Submission #72404319

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
template<typename T,typename U>
istream& operator>>(istream& i, pair<T,U>& p) { i >> p.first >> p.second; return i; }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()
#define XY(t) t.x, t.y

const int maxn = int(2e5) + 10;
const int maxm = int(2e5) + 10;
// const int M = 262144;
// const int mod = 998'244'353;
// const int mod = int(1e9) + 7;
// const int inf = (1ll<<30);
const ll inf = (1ll<<60);

int n, m;
struct E { int x, y, c; } e[maxm];

vector<int> eiv[maxn];

ll d[maxn];

void dijk(int V, int sv) {
    priority_queue<pll> pq;
    fill(d+1, d+V+1, inf);

    d[sv] = 0; pq.emplace(0, sv);
    while (pq.size()) {
        auto [md, x] = pq.top(); pq.pop();
        if (-md != d[x]) continue;
        for (int ei: eiv[x]) { auto &ee = e[ei];
            int y = ee.y;
            if (d[y] > -md + ee.c) {
                d[y] = -md + ee.c;
                pq.emplace(-d[y], y);
            }
        }
    }
}

int main()
{
    cppio();
    cin >> n >> m;
    rrep(i, m) {
        cin >> e[i].x >> e[i].y >> e[i].c;
        eiv[e[i].x].pb(i);
    }

    eiv[n+1].pb(1);

    dijk(n+1, n+1);

    if (d[e[1].x] == inf) cout << "-1\n";
    else cout << d[e[1].x] << '\n';

	return 0;
}

Submission Info

Judge Result