제출 #227103

#제출 시각아이디문제언어결과실행 시간메모리
227103Uzumaki_NaturooCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
402 ms18648 KiB
/// You just can't beat the person who never gives up /// ICPC next year #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include<bits/stdc++.h> using namespace std ; const int N = 1e5+5 ; int n ,m ,s ,t ,u ,v ,a ,b ,c ; vector<pair<int,int>> adj[N] ; long long dis[3][N] ; void dijkstra(int src,long long d[]){ for(int i=0;i<N;++i) d[i] = 1e18 ; d[src] = 0 ; priority_queue<pair<long long,int>> pq ; pq.push({0,src}); while(pq.size()){ int p = pq.top().second ; pq.pop() ; for(auto e:adj[p]){ int ch = e.first ; int cst = e.second ; if(d[ch]<=d[p]+cst) continue ; d[ch] = d[p]+cst ; pq.push({-d[ch],ch}); } } } long long mem[N] ; long long dfs(int p,long long a,long long b){ long long&ret = mem[p]; if(~ret) return ret ; ret = a + b ; for(auto e:adj[p]){ int ch = e.first ; int cst = e.second ; if(dis[0][ch]!=dis[0][p]-cst) continue ; long long aa = min(a ,dis[1][ch]) ; long long bb = min(b ,dis[2][ch]) ; ret = min(ret ,dfs(ch,aa,bb)) ; } return ret ; } int main(){ scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v); while(m--){ scanf("%d%d%d",&a,&b,&c); adj[a].push_back({b,c}); adj[b].push_back({a,c}); } dijkstra(s,dis[0]) ; dijkstra(u,dis[1]) ; dijkstra(v,dis[2]) ; memset(mem,-1,sizeof mem); printf("%lld",min(dfs(t,dis[1][t],dis[2][t]) ,dis[1][v])) ; return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...