fork download

copy

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
 
#include<stack>
#include<bitset>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include<unordered_map>
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
 
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(r,v) for(auto r:v)
 
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define pc()  pop_back()
 
#define ull unsigned long long
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
 
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
#define endl '\n'
 
#define st stack<int>
 
 
 
#define vl vector<long long>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvi vector<vi>
#define vs vector<string>
 
#define mod 1000000007
 
#define un  unordered_map<int,int>
#define mii map<int,int>
 
#define Sort(a) sort(all(a))
#define ED(a) Sort(a), a.erase(unique(all(a)), a.end())//removing all duplicates
 
#define max3(a, b, c)   max(a, max(b, c))
#define min3(a, b, c)   min(a, min(b, c))
#define Max(a)       *max_element(all(a))
#define Min(a)       *min_element(all(a))
#define MaxP(a)       max_element(all(a)) - a.begin()
#define MinP(a)        min_element(all(a)) - a.begin()
 
#define allUpper(a)     transform(all(a), a.begin(), :: toupper)
#define allLower(a)     transform(all(a), a.begin(), :: tolower)
 
#define rev(a)          reverse(all(a))
#define ub(v,k)          upper_bound(all(v), k) - v.begin()
#define lb(v,k)          lower_bound(all(v), k) - v.begin()
#define adv(a,n)        advance(auto it:a,n)
#define RSort(a)         sort(a.rbegin(),a.rend()) //decending order
#define cnt(v,a)             count(all(v),a)
#define bs(v,a)           binary_search(all(v),a)
#define mmax(v)           *max_element(all(v))
#define mmin(v)           *min_element(all(v))
#define popcount(mask)                       __builtin_popcount(mask) // count set bit
#define popcountLL(mask)                     __builtin_popcountll(mask) // for long long
#define X real() // useful for working with #include <complex> for computational geometry
#define Y imag()
#define ll long long
#define ss second
#define ff first
 
#define trace1(x)                           cerr << #x << ": " << x << endl;
#define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f)            cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
template <typename T> T gcd(T a, T b) { while (b) b ^= a ^= b ^= a %= b; return a; }
template <typename T> T setbit(T mask, T pos) { return mask |= (1 << pos); }
template <typename T> T resetbit(T mask, T pos) { return mask &= ~(1 << pos); }
template <typename T> T togglebit(T mask, T pos) { return mask ^= (1 << pos); }
template <typename T> T checkbit(T mask, T pos) { return (bool)(mask & (1 << pos)); }
template <typename T> T lcm(T a, T b) { return (a / gcd(a, b)) * b; }
 
 
 
template <typename T> T modu(T a, T b) { return (a < b ? a : a % b); }
template<typename T> T mod_neg(T a, T b) { a = mod(a, b); if (a < 0) { a += b; } return a; }
 
template <typename T>T expo(T e, T n) { T x = 1, p = e; while (n) { if (n & 1)x = x * p; p = p * p; n >>= 1; } return x; }
template<typename T> T mod_inverse(T a, T n) { T x, y; T d = extended_euclid(a, n, x, y); return (d > 1 ? -1 : mod_neg(x, n)); }
 
template <typename T>T power(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mod(x * p, m); p = mod(p * p, m); n >>= 1; } return x; }
template <typename T>T powerL(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mulmod(x, p, m); p = mulmod(p, p, m); n >>= 1; } return x; }
 
bool Pow2(int n) {
    return n && (!(n & (n - 1)));
}
void printc(vc& result) {
    aut(r, result) cout << r << " ";
    cout << endl;
}
void printl(vl& result) {
    aut(r, result) cout << r << " ";
    cout << endl;
}
void print(vi& result) {
    aut(r, result) cout << r << " ";
    cout << endl;
}
 
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
/*ll modInv(ll a) { return power(a, mod - 2) % mod; }
ll fact[1], inv[1];
void factorial(ll n) {
    fact[0] = 1;
    for (ll i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i;
        fact[i] %= mod;
    }
}
void InvFactorial(ll n) {
    inv[0] = 1;
    for (ll i = 1; i <= n; i++)
        inv[i] = modInv(fact[i]);
}
ll ncr(ll n, ll r) {
    if (n < r || n < 0 || r < 0)
        return 0;
    ll b = inv[n - r];
    ll c = inv[r];
    ll a = fact[n] * b;
    a %= mod;
    a *= c;
    a %= mod;
    return a;
}*/
//ifstream cin("b_read_on.txt"); ofstream cout("output3.txt");
//Use (<<) for multiplication
//Use (>>) for division
//ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed;cerr.tie(NULL);
// find_by_order -> value at index
// order_of_key -> index of value
// while using (1<<i) use ((ll)1<<(ll)i) 
// in Floyd-Warshall Algo, k is outer loop 
// If an element was not initially in map and if asked mp[a],the element gets inserted 
// a%=mod take a lot of time... try to use it minimum and use memset as it reduces a lot of time usage...use if(a>=mod) a%=mod
//cout<<(double) can be harmful , always use printf(%.9llf)...take scanf("%lf",&p[i][j]) as input , not llf;
//use s.erase(it++) for erasing iterator and then moving to the next one
//never use adj.resize(n) as value is persistent, always erase
//use __builtin_popcountll() for ll
// no of prime numbers in range : (70,19) , (1000,168) , (100000,1229) , (sqrt(10^9),3409) ;
//always check the use of segment tree using bottom-up dp
vector<pair<int, int>> adj[100001];
vb vis(100001);
vi dis(100001,INF);
vi par(100001, -1);
void disktraw(int s,int n) {
    dis[s] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int a = pq.top().ss;
        pq.pop();
        if (vis[a]) continue;
        vis[a] = true;
        for (auto it : adj[a]) {
            int b = it.ff;
            int w = it.ss;
            if (dis[a] + w < dis[b]) {
                par[b] = a;
                dis[b] = dis[a] + w;
                pq.push({ -dis[b],b });
            }
        }
 
    }
    if (vis[n] == false) cout << -1 << endl;
    else {
        vi path;
        for (int i = n; i != -1; i = par[i]) {
            path.pb(i);
        }
        reverse(all(path));
        print(path);
 
    }
}
 
 
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test;
    test = 1;
    // cin >> test;
    while (test--) {
        int n, m;
        cin >> n >> m;
        vector<tuple<int, int, int>> edges;
        while (m--) {
            int a, b, w;
            cin >> a >> b >> w;
            adj[a].push_back({ b,w });
            adj[b].push_back({ a,w });
 
        }
        disktraw(1,n);
    }
 
}
 
 
 
 
 
 
 
 

Main.java:1: error: illegal character: '#'
#include <string>
^
Main.java:1: error: class, interface, or enum expected
#include <string>
         ^
Main.java:2: error: illegal character: '#'
#include <vector>
^
Main.java:3: error: illegal character: '#'
#include <algorithm>
^
Main.java:4: error: illegal character: '#'
#include <numeric>
^
Main.java:5: error: illegal character: '#'
#include <set>
^
Main.java:6: error: illegal character: '#'
#include <map>
^
Main.java:7: error: illegal character: '#'
#include <queue>
^
Main.java:9: error: illegal character: '#'
#include<stack>
^
Main.java:10: error: illegal character: '#'
#include<bitset>
^
Main.java:11: error: illegal character: '#'
#include <iostream>
^
Main.java:12: error: illegal character: '#'
#include <sstream>
^
Main.java:13: error: illegal character: '#'
#include <cstdio>
^
Main.java:14: error: illegal character: '#'
#include <cmath>
^
Main.java:15: error: illegal character: '#'
#include <ctime>
^
Main.java:16: error: illegal character: '#'
#include <cstring>
^
Main.java:17: error: illegal character: '#'
#include <cctype>
^
Main.java:18: error: illegal character: '#'
#include <cassert>
^
Main.java:19: error: illegal character: '#'
#include <limits>
^
Main.java:20: error: illegal character: '#'
#include <functional>
^
Main.java:21: error: illegal character: '#'
#include<unordered_map>
^
Main.java:23: error: illegal character: '#'
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
^
Main.java:23: error: class, interface, or enum expected
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
                               ^
Main.java:23: error: class, interface, or enum expected
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
                                            ^
Main.java:25: error: illegal character: '#'
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
^
Main.java:25: error: class, interface, or enum expected
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
                                        ^
Main.java:25: error: class, interface, or enum expected
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
                                                     ^
Main.java:26: error: illegal character: '#'
#define aut(r,v) for(auto r:v)
^
Main.java:28: error: illegal character: '#'
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
^
Main.java:28: error: class, interface, or enum expected
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
                                             ^
Main.java:28: error: class, interface, or enum expected
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
                                                              ^
Main.java:29: error: illegal character: '#'
#define all(o) (o).begin(), (o).end()
^
Main.java:30: error: illegal character: '#'
#define pb(x) push_back(x)
^
Main.java:31: error: illegal character: '#'
#define pc()  pop_back()
^
Main.java:33: error: illegal character: '#'
#define ull unsigned long long
^
Main.java:34: error: illegal character: '#'
#define mp(x,y) make_pair((x),(y))
^
Main.java:35: error: illegal character: '#'
#define mset(m,v) memset(m,v,sizeof(m))
^
Main.java:37: error: illegal character: '#'
#define INF 0x3f3f3f3f
^
Main.java:38: error: illegal character: '#'
#define INFL 0x3f3f3f3f3f3f3f3fLL
^
Main.java:40: error: illegal character: '#'
#define endl '\n'
^
Main.java:40: error: class, interface, or enum expected
#define endl '\n'
        ^
Main.java:42: error: illegal character: '#'
#define st stack<int>
^
Main.java:46: error: illegal character: '#'
#define vl vector<long long>
^
Main.java:47: error: illegal character: '#'
#define vi vector<int>
^
Main.java:48: error: illegal character: '#'
#define vb vector<bool>
^
Main.java:49: error: illegal character: '#'
#define vc vector<char>
^
Main.java:50: error: illegal character: '#'
#define pii pair<int,int>
^
Main.java:51: error: illegal character: '#'
#define vpii vector<pii>
^
Main.java:52: error: illegal character: '#'
#define vvi vector<vi>
^
Main.java:53: error: illegal character: '#'
#define vs vector<string>
^
Main.java:55: error: illegal character: '#'
#define mod 1000000007
^
Main.java:57: error: illegal character: '#'
#define un  unordered_map<int,int>
^
Main.java:58: error: illegal character: '#'
#define mii map<int,int>
^
Main.java:60: error: illegal character: '#'
#define Sort(a) sort(all(a))
^
Main.java:61: error: illegal character: '#'
#define ED(a) Sort(a), a.erase(unique(all(a)), a.end())//removing all duplicates
^
Main.java:63: error: illegal character: '#'
#define max3(a, b, c)   max(a, max(b, c))
^
Main.java:64: error: illegal character: '#'
#define min3(a, b, c)   min(a, min(b, c))
^
Main.java:65: error: illegal character: '#'
#define Max(a)       *max_element(all(a))
^
Main.java:66: error: illegal character: '#'
#define Min(a)       *min_element(all(a))
^
Main.java:67: error: illegal character: '#'
#define MaxP(a)       max_element(all(a)) - a.begin()
^
Main.java:68: error: illegal character: '#'
#define MinP(a)        min_element(all(a)) - a.begin()
^
Main.java:70: error: illegal character: '#'
#define allUpper(a)     transform(all(a), a.begin(), :: toupper)
^
Main.java:71: error: illegal character: '#'
#define allLower(a)     transform(all(a), a.begin(), :: tolower)
^
Main.java:73: error: illegal character: '#'
#define rev(a)          reverse(all(a))
^
Main.java:74: error: illegal character: '#'
#define ub(v,k)          upper_bound(all(v), k) - v.begin()
^
Main.java:75: error: illegal character: '#'
#define lb(v,k)          lower_bound(all(v), k) - v.begin()
^
Main.java:76: error: illegal character: '#'
#define adv(a,n)        advance(auto it:a,n)
^
Main.java:77: error: illegal character: '#'
#define RSort(a)         sort(a.rbegin(),a.rend()) //decending order
^
Main.java:78: error: illegal character: '#'
#define cnt(v,a)             count(all(v),a)
^
Main.java:79: error: illegal character: '#'
#define bs(v,a)           binary_search(all(v),a)
^
Main.java:80: error: illegal character: '#'
#define mmax(v)           *max_element(all(v))
^
Main.java:81: error: illegal character: '#'
#define mmin(v)           *min_element(all(v))
^
Main.java:82: error: illegal character: '#'
#define popcount(mask)                       __builtin_popcount(mask) // count set bit
^
Main.java:83: error: illegal character: '#'
#define popcountLL(mask)                     __builtin_popcountll(mask) // for long long
^
Main.java:84: error: illegal character: '#'
#define X real() // useful for working with #include <complex> for computational geometry
^
Main.java:85: error: illegal character: '#'
#define Y imag()
^
Main.java:86: error: illegal character: '#'
#define ll long long
^
Main.java:87: error: illegal character: '#'
#define ss second
^
Main.java:88: error: illegal character: '#'
#define ff first
^
Main.java:90: error: illegal character: '#'
#define trace1(x)                           cerr << #x << ": " << x << endl;
^
Main.java:90: error: illegal character: '#'
#define trace1(x)                           cerr << #x << ": " << x << endl;
                                                    ^
Main.java:91: error: illegal character: '#'
#define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
^
Main.java:91: error: class, interface, or enum expected
#define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
        ^
Main.java:91: error: illegal character: '#'
#define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
                                                    ^
Main.java:91: error: illegal character: '#'
#define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
                                                                                ^
Main.java:92: error: illegal character: '#'
#define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
^
Main.java:92: error: class, interface, or enum expected
#define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
        ^
Main.java:92: error: illegal character: '#'
#define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
                                                    ^
Main.java:92: error: illegal character: '#'
#define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
                                                                                ^
Main.java:92: error: illegal character: '#'
#define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
                                                                                                            ^
Main.java:93: error: illegal character: '#'
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
^
Main.java:93: error: class, interface, or enum expected
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
        ^
Main.java:93: error: illegal character: '#'
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
                                                    ^
Main.java:93: error: illegal character: '#'
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
                                                                                ^
Main.java:93: error: illegal character: '#'
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
                                                                                                            ^
Main.java:93: error: illegal character: '#'
#define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
                                                                                                                                        ^
Main.java:94: error: illegal character: '#'
#define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
^
Main.java:94: error: class, interface, or enum expected
#define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
        ^
Main.java:94: error: illegal character: '#'
#define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
                                                    ^
Main.java:94: error: illegal character: '#'
#define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
                                                                                ^
100 errors

Standard output is empty