19:I[48803,["6079","static/chunks/363642f4-4672ca396f99db0d.js","5000","static/chunks/5000-a7bfe5b9669501e3.js","5653","static/chunks/5653-e83dcf6c883f2fed.js","1394","static/chunks/1394-b96c40fff0826c8c.js","7412","static/chunks/7412-44bfc7df6d166700.js","9362","static/chunks/9362-6e86a7341ceee1cd.js","8720","static/chunks/8720-56867bcc82acef59.js","7881","static/chunks/7881-fa5bad7aa783c72e.js","3692","static/chunks/3692-317eca9943285a39.js","9211","static/chunks/9211-d3f977dbde988018.js","9791","static/chunks/app/submission/%5Bid%5D/page-52998aeb8359bb9f.js"],"CodeViewer"] 1a:T4ce,#include #include #include #define INF 1e9 #define int long long #define endl "\n" using namespace std; int N, E, v1, v2; vector> edge[801]; int ans; void Input() { cin >> N >> E; for (int i=0;i> a >> b >> c; edge[a].push_back({c,b}); edge[b].push_back({c,a}); } cin >> v1 >> v2; } int Dijkstra(int s, int e) { vector dist(N+1,INF); dist[s] = 0; priority_queue, vector>, greater<>> PQ; PQ.push({0,s}); while(!PQ.empty()) { int now = PQ.top().second, cost = PQ.top().first; PQ.pop(); for (pair i : edge[now]) { int nxt = i.second, n_cost = i.first; if (dist[nxt] > cost + n_cost) { dist[nxt] = cost + n_cost; PQ.push({cost + n_cost, nxt}); } } } return dist[e]; } void Solve() { int a = Dijkstra(1,v1), b = Dijkstra(1,v2), c = Dijkstra(v1,v2), d = Dijkstra(v1,N), e = Dijkstra(v2,N); ans = min(a+c+e, b+c+d); if (ans >= INF) ans = -1; } int main() { Input(); Solve(); cout << ans; }

제출 #16625

제출 정보

제출 결과

제출 코드

찾은 반례