제출 #948596

#제출 시각아이디문제언어결과실행 시간메모리
948596phone64bitCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
238 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mxN = 1e5+10; struct edge { int u, v; }; struct path { int dest; ll w; }; struct Q { int src; ll w; vector<edge> p; bool operator < (const Q&rhs) const { return w>rhs.w; } }; vector<path> edges[mxN]; bitset<mxN> vs; ll dp[mxN], k_dp[mxN], ans = 1e18; int n,m,s,t,u,v; priority_queue<Q> pq; int main() { for(int i=0; i<mxN; i++) dp[i]=1e18; scanf("%d%d%d%d%d%d", &n,&m,&s,&t,&u,&v); while(m--) { int u, v; ll w; scanf("%d%d%lld", &u, &v, &w); edges[u].push_back({v, w}); edges[v].push_back({u, w}); } pq.push({s, 0, {}}); dp[s]=0; while(!pq.empty()) { auto [src, w, p] = pq.top(); pq.pop(); if(src==t) { for(auto x: p) edges[x.u].push_back({x.v, 0}), edges[x.v].push_back({x.u, 0}); break; } for(auto c: edges[src]) { if(dp[c.dest]>c.w+w) { dp[c.dest]=c.w+w; p.push_back({src, c.dest}); pq.push({c.dest, dp[c.dest], p}); p.pop_back(); } } } for(int i=0; i<mxN; i++) dp[i]=1e18; pq.push({u, 0}); dp[u]=0; while(!pq.empty()) { auto [src, w, p] = pq.top(); pq.pop(); if(src==v) { printf("%lld", w); break; } for(auto c: edges[src]) { if(dp[c.dest]>c.w+w) { dp[c.dest]=c.w+w; pq.push({c.dest, dp[c.dest]}); } } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d%d%d%d%d%d", &n,&m,&s,&t,&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:34:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...