1a:I[48803,["6079","static/chunks/363642f4-ca12a5ed7d30075e.js","5653","static/chunks/5653-10777e0e1fc92dce.js","5000","static/chunks/5000-a7bfe5b9669501e3.js","8501","static/chunks/8501-12247bfa9b4a3a0d.js","7961","static/chunks/7961-b9b64ba388cef309.js","3729","static/chunks/3729-8164898f6bdc738c.js","8720","static/chunks/8720-56867bcc82acef59.js","8324","static/chunks/8324-1983729ec379e9d8.js","9211","static/chunks/9211-c08bacb1ba75336f.js","9791","static/chunks/app/submission/%5Bid%5D/page-abe92e013e824763.js"],"CodeViewer"] 1b:T653,#include #include #include #include #include using namespace std; int n, e; vector > adj[200001]; int v1, v2; int dist[801]; int s_v1, s_v2, v1_v2, v1_e, v2_e; void dijk(int start){ fill(dist, dist + 801, INT_MAX); priority_queue , vector >, greater >> pq; dist[start] = 0; pq.push({dist[start], start}); while (!pq.empty()){ int d = pq.top().first; int curr = pq.top().second; pq.pop(); if (d > dist[curr]) continue; for (pair i : adj[curr]){ int next = i.first; int weight = i.second; if (weight + dist[curr] < dist[next]){ dist[next] = weight + dist[curr]; pq.push({dist[next], next}); } } } } int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> e; for (int s = 0; s < e; ++s){ int a, b, c; cin >> a >> b >> c; adj[a].push_back(make_pair(b, c)); adj[b].push_back(make_pair(a, c)); } cin >> v1 >> v2; dijk(1); s_v1 = dist[v1]; s_v2 = dist[v2]; dijk(v1); v1_v2 = dist[v2]; v1_e = dist[n]; dijk(v2); v2_e = dist[n]; if (v1_v2 == INT_MAX || ){ cout << "-1"; return 0; } int ans = INT_MAX; ans = min(ans, s_v1 + v1_v2 + v2_e); ans = min(ans,

제출 #73358

제출 정보

제출 결과

제출 코드

찾은 반례