Submission #72404458

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using LL = long long;
using pii = pair<int, int>;
#define fi first
#define se second
constexpr int MAXN = 2e5 + 5, mod = 998244353;
int n, m, s, t, sw;
LL dist[MAXN];
bool vis[MAXN];
vector<pii> G[MAXN];
inline void dijkstra() {
	for (int i = 1; i <= n; ++i) dist[i] = 1e18;
	dist[s] = sw;
	priority_queue<pair<LL, int> > q;
	q.emplace(-sw, s);
	while (!q.empty()) {
		int u = q.top().se; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto P : G[u]) {
			int v = P.fi;
			if (dist[v] > dist[u] + P.se) {
				dist[v] = dist[u] + P.se;
				q.emplace(-dist[v], v);
			}
		}
	}
}
int main() {
	IOS;
	cin >> n >> m;
	for (int u, v, w, i = 1; i <= m; ++i) {
		cin >> u >> v >> w;
		if (i == 1) s = v, sw = w, t = u;
		G[u].emplace_back(v, w);
	}
	dijkstra();
	if (!vis[t]) cout << "-1";
	else cout << dist[t];
	return 0;
}

Submission Info

Judge Result