propblem_solving/B_B.cpp at master · Arnob-sen/propblem_solving · GitHub

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
106
107
108
109
110
111
112
113

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define vc vector
vector<ll> parent;
#define IOS                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);

const ll inf = 1e18;
const ld ep = 0.0000001;
const ld pi = acos(-1.0);
const ll md = 1000000007;

int vis[100005], dis[100005];
vii adj[100005];

ll n, m;
void dijkstra()
{

    priority_queue<pii, vii, greater<pii>> pq;
    pq.push({0, 1});
    while (!pq.empty())
    {
        // if (vis[n])
        //     return;
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        //  ans.push_back(u);

        for (auto x : adj[u])
        {
            int v = x.first;
            ll w = x.second;

            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                pq.push(make_pair(dis[v], v));
                parent[v] = u;
            }
        }
    }
}
void printpath(ll n)
{
    if (parent[n] == -1)
    {
        cout << n;
        return;
    }
    printpath(parent[n]);
    cout << " " << n;
}
void solve()
{

    cin >> n >> m;
    parent.assign(n + 1, -1);

    for (ll i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (int i = 2; i <= n; i++)
        dis[i] = inf;
    dijkstra();
    if (dis[n] == inf)
        cout << "-1\n";
    else
    {
        vector<ll> ans;
        for (int i = n; i != -1; i = parent[i])
            ans.push_back(i);

        reverse(ans.begin(), ans.end());
        for (ll i = 0; i < ans.size(); i++)
            cout << ans[i] << " ";
    }
    // for (int i = 0; i < parent.size(); i++)
    //   cout << parent[i] << " ";
    // cout << ans.size() << " ";
}
signed main()
{
    IOS;

    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
        // cout<<'\n';
    }
}