프로그래밍

https://www.acmicpc.net/problem/14938

[난이도] Gold4
[유형] 플로이드 와샬

[풀이]
플로이드 와샬로 모든 지점간 거리를 구한 후
각 점에서 M거리 이하인 지점의 아이템 개수를 모두 더한 값의 최솟값이 정답이다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14938.cpp

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,R,item[101],dist[101][101],inf=9e8,ans;
int main(){
    scanf("%d%d%d",&N,&M,&R);
    for(int i=1;i<=N;i++) scanf("%d",&item[i]);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i!=j) dist[i][j] = inf;
        }
    }
    while(R--){
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        dist[a][b] = min(dist[a][b],l);
        dist[b][a] = min(dist[b][a],l);
    }

    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);

    for(int i=1;i<=N;i++){
        int sum=0;
        for(int j=1;j<=N;j++){
            if(dist[i][j]<=M) sum+=item[j];
        }
        ans = max(ans,sum);
    }
    printf("%d",ans);
}

https://www.acmicpc.net/problem/1719

[난이도] Gold4
[유형] 플로이드 워셜

[풀이]
각 집하장간 최단거리는 플로이드 워셜 알고리즘으로 구할 수 있다.
이 문제에서는 플로이드로 i,j의 최단 경로를 구했을 때, i다음 가야하는
집하장을 구해야한다. 이것을 path[i][j]에 저장한다.
경로를 갱신할 때 다음 중간에 거쳐가야할 집하장을 k라고 하면
path[i][j] = path[i][k]로 갱신하여 모든 i,j 쌍에 대해 path[i][j]를 구할 수 있다.

#include <cstdio>
int N,M,dist[201][201],inf=9e8,path[201][201];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            dist[i][j]=inf;
            if(i==j) dist[i][j]=0;
        }
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dist[a][b]=dist[b][a]=c;
        path[a][b]=b;
        path[b][a]=a;
    }
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) {
                if(dist[i][j] > dist[i][k]+dist[k][j]){
                   dist[i][j] = dist[i][k]+dist[k][j];
                   if(i!=k) path[i][j] = path[i][k];
                }
            }    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++) {
            if(path[i][j]) printf("%d ",path[i][j]);
            else printf("%c ",'-');
        }        
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1719.cpp

https://www.acmicpc.net/problem/11562

[난이도] Gold4
[유형] 다익스트라, 플로이드 워셜

[풀이]
원래 길이 있는 경우에는 비용이 안드므로 0의 cost,
단방향 통행만 가능하면 그 반대로 오는길은 1의 cost를 준 뒤
다익스트라를 돌려주면 몇개의 단방향 길을 바꿔야 하는지 알 수 있다.
모든 쿼리마다 다익스트라를 돌리면 시간초과가 나므로 출발점 N개에 대해
한번씩만 호출되도록 한다.

(플로이드 워셜로 풀면 훨씬 간결하게 풀 수 있다.)

#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
int N,M,K,inf=9e8;
vector<pair<int,int>> adj[251];
int s,e,dist[251][251];
void dijk(){
    fill(dist[s],dist[s]+N+1,inf);
    priority_queue<pair<int,int>> pq;
    dist[s][s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto qt = pq.top(); pq.pop();
        int cur = qt.second, cd=-qt.first;
        if(cd > dist[s][cur]) continue;
        for(auto next : adj[cur]){
            int nxt = next.first, nd = cd+next.second;
            if(dist[s][nxt] > nd){
                dist[s][nxt] = nd;
                pq.push({-nd,nxt});
            }
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,k;
        scanf("%d%d%d",&u,&v,&k);
        adj[u].push_back({v,0});
        adj[v].push_back({u,!k});
    }
    scanf("%d",&K);
    memset(dist,-1,sizeof(dist));
    while(K--){
        scanf("%d%d",&s,&e);
        if(dist[s][s]==-1) dijk();
        printf("%d\n",dist[s][e]);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11562.cpp

https://www.acmicpc.net/problem/11780

[난이도] Gold4
[유형] 플로이드 와샬

[풀이]
플로이드 와샬의 경로까지 출력해야 하는 문제이다.
최단경로를 갱신할 때 경유지 i,j의 경유지 k를 path[i][j]에 저장해놓고
이것을 이용해 재귀함수로 경로를 출력한다.

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int N,M,dist[101][101],path[101][101],INF=9e8;
void prt(int i,int j,vector<int>& tmp){
    if(i==j) {
        tmp.push_back(i);
        return;
    }
    int p = path[i][j];
    prt(i,p,tmp);
    if(i!=p) prt(p,j,tmp);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) if(i!=j) dist[i][j]=INF;  
             
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(dist[a][b] > c){
           dist[a][b] = c;
           path[a][b] = a;
        }
    }
    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(dist[i][j]>dist[i][k]+dist[k][j]){
                   dist[i][j]=dist[i][k]+dist[k][j];
                   path[i][j]=k;
                }
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            printf("%d ",dist[i][j]==INF ? 0 : dist[i][j]);
        puts("");
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(!dist[i][j]) printf("0");
            else {
                vector<int> tmp;
                prt(i,j,tmp);
                tmp.push_back(j);
                printf("%d ",tmp.size());
                for(auto k : tmp) printf("%d ",k);
            }
            puts("");
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11780.cpp