택배

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
 
using namespace std;
 
int tc,n, d, c;
vector<pair<int,int> > map[20000];
int visit[20000];
int dist[20000];
int node, edge;
int INF = 987654321;
int mapp[200][200];
 
 
void dijkstra(int start) {
    visit[start] = 0;
    priority_queue<pair<int, long long> > pq;
    pq.push(make_pair(start, 0));
    while (!pq.empty()) {
        int current = pq.top().first;
        int distance = -pq.top().second;
        pq.pop();
        if (visit[current] < distance) continue;
        for(int i = 0; i< map[current].size(); i++){
            int next = map[current][i].first;
            int nextDistance = distance + map[current][i].second;
            if (nextDistance < visit[next]) {
                visit[next] = nextDistance;
                dist[next] = current+1;
                pq.push(make_pair(next, -nextDistance));
            }
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> node >> edge;
 
 
    for (int i = 0; i < edge; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        map[a - 1].push_back({b-1,c});
        map[b - 1].push_back({ a - 1,c });
 
    }
 
    for(int i = 0; i < node;i++){
        for (int i = 0; i < node; i++) {
            visit[i] = INF;
        }
        dijkstra(i);
        for (int j = 0; j < node; j++) {
            if (visit[j] != INF && i != j) {
                mapp[j][i] = dist[j];
            }
        }
    }
 
    for(int i = 0;i < node; i++){
        for(int j = 0; j < node; j++){
            if(i != j)
            cout<<mapp[i][j]<<' ';
            else cout<<'-'<<' ';
        }cout<<'\n';
    }
 
    return 0;
}
 

다익스트라 문제, 다익스트라알고리즘 복습하면서 풀어본 문제

다익스트라와 최소신장트리는 자꾸까먹는것같아서 복습차원에서 다시푼문제