Shortest Path Problem - Answer code

나의 글 중 < Shortest Path Problem > 글에 대한 정답 코드들이다. 혹시 풀어보고 싶은 사람이 있을까봐 분리해둔다.

//17071

#include <stdio.h>
#include <tuple>
#include <queue>
#include <cstring>
using namespace std;

int dist[500001][2] = {};
int main(void) {
    int n = 0;
    int k = 0;
    scanf("%d %d",&n, &k);
    memset(dist, -1, sizeof(dist));
    queue<pair<int,int>> q;
    q.push(make_pair(n,0));
    dist[n][0] = 0;
    while(!q.empty()) {
        int x = q.front().first;
        int t = q.front().second;
        q.pop();
        for(int y : {x+1,x-1,2*x}) {
            if(0 <= y && y <= 500000) {
                if(dist[y][1-t] == -1) {
                    dist[y][1-t] = dist[x][t] + 1;
                    q.push(make_pair(y,1-t));
                }
            }
        }
    }
    int ans = -1;
    for(int t = 0;;t++) {
        k+=t;
        if(k>500000) {
            break;
        }
        if(dist[k][t%2] <= t) {
            ans = t;
            break;
        }
    }
    printf("%d",ans);
}

//5719

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
 
vector<pii>g[505];
int dis[505];
vector<int>way[505];
bool check[505];
 
void dijkstra(int x) {
    dis[x] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(make_pair(0, x));
    while (!pq.empty()) {
        int now = pq.top().second;
        int wei = pq.top().first;
        pq.pop();
        if (dis[now] < wei) continue;
        for (int i = 0; i < g[now].size(); i++) {
            if (g[now][i].second == -1)continue;// 두 번째 dijkstra에서 제거된 간선 제외!
            int next = g[now][i].first;
            int ww = g[now][i].second;
            if (dis[now] + ww < dis[next]) {
                dis[next] = dis[now] + ww;
                way[next].clear(); 
                way[next].push_back(now); // 최단 경로 갱신
                pq.push(make_pair(dis[next], next));
            }
            else if (dis[now] + ww == dis[next]) {
                way[next].push_back(now); // 반드시 이렇게 next와 now를 설정해야 함!
            }
            else continue;
        }
    }
}
 
void bfs(int x) {
    queue<int>q;
    q.push(x);
    while (!q.empty()) {
        x = q.front();
        q.pop();
        if (check[x] == true) continue;
        check[x] = true;
        for (int i = 0; i < way[x].size(); i++) {
            int nx = way[x][i];
            for (int j = 0; j < g[nx].size(); j++) {
                if (g[nx][j].first == x) g[nx][j].second = -1; // 간선을 삭제
            }
            q.push(nx);
        }
    }
}
 
void init() {
    memset(g, 0, sizeof(g));
    memset(way, 0, sizeof(way));
    memset(dis, 127, sizeof(dis));
    memset(check, false, sizeof(check));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    while (1) {
        int n, m, start, end, u, v, e;
        init(); // 초기화 시켜주기
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        cin >> start >> end;
        for (int i = 0; i < m; i++) {
            cin >> u >> v >> e;
            g[u].push_back(make_pair(v, e));
        }
        int INF = dis[0];
        dijkstra(start); // start부터 모든 정점까지의 최단 거리 구함
        bfs(end); // end부터 start까지 연결된 간선들을 제거
        memset(dis, 127, sizeof(dis)); // 최단 거리를 다시 구해야 하므로
        dijkstra(start); // 다시 최단 거리 구함
        if (dis[end] == INF) cout << -1 << "\n";
        else cout << dis[end] << "\n";
    }
}

//11657

#include <stdio.h>
#include <vector>
using namespace std;
struct Edge {
    int from;
    int to;
    int cost;
};

long long int dist[501];
int inf = 100000000;
int main(void) {
    int n = 0;
    int m = 0;
    scanf("%d %d",&n,&m);
    vector<Edge> a(m);
    for (int i=0; i<m; ++i) {
        scanf("%d %d %d",&a[i].from, &a[i].to, &a[i].cost);
    }
    for (int i=1; i<=n; ++i) {
        dist[i] = inf;
    }
    dist[1] = 0;
    bool negative_cycle = false;
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<m; ++j) {
            int x = a[j].from;
            int y = a[j].to;
            int z = a[j].cost;
            if (dist[x] != inf && dist[y] > dist[x]+z) {
                dist[y] = dist[x]+z;
                if (i == n) {
                    negative_cycle = true;
                }
            }
        }
    }
    if (negative_cycle) {
        printf("-1\n");
    } else {
        for (int i=2; i<=n; ++i) {
            if (dist[i] == inf) dist[i] = -1;
            printf("%lld\n",dist[i]);
        }
    }
}

// 13141

#include <vector>
#include <stdio.h>
using namespace std;
int inf = 987654321;
int n = 0;
int m = 0;
vector<vector<int>> arr;
vector<vector<int>> dist;
double burnGraph() {
    double shortestTime = inf;
    double longestTime;
    double spentTime;
    double remainingLength;
    int longestLength;
    for(int start = 1;start<=n;++start) {
        longestTime = 0;
        for(int from = 1;from<=n;++from) {
            for(int to = 1; to <=n;++to) {
                longestLength = arr[from][to];
                if(longestLength!=-1) {
                    remainingLength = longestLength-(dist[start][to]-dist[start][from]);
                    if(remainingLength > 0) {
                        spentTime = remainingLength/2+dist[start][to];
                        if(spentTime > longestTime) {
                            longestTime = spentTime;
                        }
                    }
                }
            }
        }
        if(longestTime < shortestTime) {
            shortestTime = longestTime;
        }
    }
    return shortestTime;
}

void runFloyd() {
    for(int i = 1;i<=n;++i) {
        for(int j = 1;j<=n;++j) {
            for(int k = 1;k<=n;++k) {
                dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k]);
            }
        }
    }
}

int main(void) {
    scanf("%d %d",&n, &m);
    arr = vector<vector<int>>(n+1, vector<int>(n+1, -1));
    dist = vector<vector<int>>(n+1, vector<int>(n+1, inf));
    for(int i = 1;i<=n;++i) {
        dist[i][i] = 0;
    }
    for(int i = 0;i<m;++i) {
        int s = 0;
        int e = 0;
        int l = 0;
        scanf("%d %d %d",&s, &e, &l);
        if(arr[s][e]==-1 || arr[s][e] < l) {
            arr[s][e] = l;
            arr[e][s] = l;
        }
        if(dist[s][e]==inf || dist[s][e] > l) {
            dist[s][e] = l;
            dist[e][s] = l;
        }
    }
    runFloyd();
    printf("%.1f", burnGraph());
}