CodeForces 20C - Dijkstra

| In | 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<long long, int> Pair;
int n, m, a;
struct to { int b, w; } To;
struct dis {
    int parent;
    long long path;
} Dis[100001];
vector<to> edge[100001];
inline void Dijkstra() {
    Pair p;
    priority_queue<Pair, vector<Pair>, greater<Pair>> Queue;
    for (int i = 1; i <= n; ++i) {
        Dis[i].parent = i;
        Dis[i].path = LLONG_MAX;
    }
    Dis[1].path = 0;
    Queue.push(Pair(0, 1));
    while (!Queue.empty()) {
        p = Queue.top();
        Queue.pop();
        if (Dis[p.second].path < p.first) {
            continue;
        }
        for (int i = 0; i < edge[p.second].size(); ++i) {
            To = edge[p.second][i];
            if (Dis[To.b].path > p.first + To.w) {
                Dis[To.b].parent = p.second;
                Dis[To.b].path = p.first + To.w;				
                Queue.push(Pair(Dis[To.b].path, To.b));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    bool isPath = true;
    vector<int> path;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a >> To.b >> To.w;
        edge[a].push_back(To);
        swap(a, To.b);
        edge[a].push_back(To);
    }
    Dijkstra();
    path.push_back(n);
    while (n != 1) {
        if (Dis[n].parent == n) {
            isPath = false;
            break;
        }
        n = Dis[n].parent;
        path.push_back(n);		
    }
    if(isPath) {
        cout << 1;
        for (int i = path.size() - 2; i >= 0; --i) {
            cout << ' ' << path[i];
        }
        cout << '\n';
    }
    else { cout << "-1\n"; }
    return 0;
}