Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <algorithm>
- #include <vector>
- #include<queue>
- #include<limits.h>
- #include<functional>
- using namespace std;
- FILE *in = stdin;
- FILE *out = stdout;
- typedef pair<int, int> pii;
- int n, m;
- vector <pii> v[100005];
- long long dis[100005];
- int p[100005];
- int ans[100005];
- int main() {
- fscanf(in, "%d %d", &n, &m);
- for (int i = 1; i <= n; i++) {
- dis[i] = LLONG_MAX;
- }
- for (int i = 1; i <= m; i++) {
- int x, y, z;
- fscanf(in, "%d %d %d", &x, &y, &z);
- v[x].push_back(make_pair(z, y));
- v[y].push_back(make_pair(z, x));
- }
- dis[1] = 0;
- priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> >> pq;
- pq.push(make_pair(0, 1));
- while (!pq.empty()) {
- int pos = pq.top().second;
- pq.pop();
- for (int i = 0; i < v[pos].size(); i++) {
- if (v[pos][i].first + dis[pos] < dis[v[pos][i].second]) {
- pq.push(make_pair(v[pos][i].first + dis[pos], v[pos][i].second));
- dis[v[pos][i].second] = v[pos][i].first + dis[pos];
- p[v[pos][i].second] = pos;
- }
- }
- }
- int now = n;
- int dude = 1;
- int check = 1;
- bool bro = false;
- while (now != 1) {
- ans[dude] = now;
- dude++;
- now = p[now];
- if (check > n) {
- bro = true;
- break;
- }
- check++;
- }
- if (bro) fprintf(out, "-1");
- else {
- fprintf(out, "1 ");
- for (int i = dude - 1; i >= 1; i--) {
- fprintf(out, "%d ", ans[i]);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement