2611 - 자동차 경주

다익스트라에서 큐의 우선순위를 "가중치가 높은 노드"로 바꾸면 된다.

중간에 시작 노드를 지나갈 수 없으므로 (처음을 제외한) 시작 노드 이후의 경로는 탐색하지 않도록 한다.

경로 출력은 큐에 넣는 작업을 할때마다 그 때의 이전 노드를 따로 저장 (즉, 어디서부터 왔는 가를 저장)하여 마지막엔 시작 노드로부터 그 역순으로 따라올라가면 경로를 얻을 수 있다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;
typedef pair<int,int> ii;

void solve(vector<ii> adj[], int n, int s){
    vector<int> cost(n, 0);
    priority_queue<ii> q;
    q.push({0, s});
    cost[s] = 0;
    bool looped = false;
    vector<int> trace(n, 0);
    while(!q.empty()){
        int pos = q.top().second;
        int dist = q.top().first;
        q.pop();
        
        if(pos == s){
            if(looped) continue;
            looped = true;
        }
        
        for(int i=0; i<adj[pos].size(); ++i){
            ii& next = adj[pos][i];
            if(dist + next.second < cost[next.first]) continue;
            q.push({dist+next.second, next.first});
            cost[next.first] = dist+next.second;
            trace[next.first] = pos;
        }
    }
    printf("%d\n", cost[s]);
    int pos = trace[s];
    vector<int> ret(1, 0);
    while(pos != s){
        ret.push_back(pos);
        pos = trace[pos];
    }
    if(ret.size() > 1) printf("1 ");
    for(int i=(int)ret.size()-1; i>=0; --i)
        printf("%d ", ret[i]+1);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<ii> adj[n];
    while(m--){
        int v, w, x;
        scanf("%d %d %d", &v, &w, &x);
        adj[v-1].push_back({w-1, x});
    }
    solve(adj, n, 0);
    return 0;
}