제출 #70806

#제출 시각아이디문제언어결과실행 시간메모리
708063zpCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
907 ms20488 KiB
#include<bits/stdc++.h> #define mn 100009 #define pb push_back using namespace std; long long n, m, S, T, U, V; long long f[mn]; vector<int> v[mn], l[mn]; void Dij(long long k, long long *D){ priority_queue<pair<int,int> > q; q.push({0,k}); for(long long i = 1; i <= n; i++) D[i] = 1e18, f[i] = 0; D[k] = 0; while(q.size()){ long long x = q.top().second; q.pop(); if(f[x]) continue; f[x] = 1; for(long long i = 0; i < v[x].size(); i++){ if(f[v[x][i]] == 0 && D[v[x][i]] > D[x] + l[x][i]){ D[v[x][i]] = D[x] + l[x][i]; q.push({-D[v[x][i]], v[x][i]}); } } } } long long du[mn], dv[mn], ds[mn], dt[mn], mindu[mn], mindv[mn]; void specDIJ(){ priority_queue<pair<int,int> > q; q.push({0,T}); for(long long i = 1; i <= n; i++) dt[i] = 1e18, mindu[i] = du[i], mindv[i] = dv[i] ,f[i] = 0; dt[T] = 0; while(q.size()){ long long x = q.top().second; q.pop(); if(f[x]) continue; f[x] = 1; for(long long i = 0; i < v[x].size(); i++){ long long p = v[x][i]; if(dt[p] > dt[x] + l[x][i]){ dt[p] = dt[x] + l[x][i]; mindu[p] = min(mindu[x], du[p]); mindv[p] = min(mindv[x], dv[p]); q.push({-dt[p], p}); } if(dt[p] == dt[x] + l[x][i]){ mindu[p] = min(mindu[p], mindu[x]); mindv[p] = min(mindv[p], mindv[x]); } } } } main(){ cin >> n >> m >> S >> T >> U >> V; for(long long i = 0 ;i < m; i++){ long long a, b, c; cin >> a>> b >> c; v[a].pb(b); v[b].pb(a); l[a].pb(c); l[b].pb(c); } Dij(S,ds); Dij(U,du); Dij(V,dv); specDIJ(); long long ans = 1e18; for(long long i = 1; i <= n; i++){ if(ds[i] + dt[i] == ds[T]){ ans = min(ans, du[i]); //ans = min(ans, dv[i] + mindu[i]); //ans = min(ans, du[i] + mindv[i]); } } cout << min(ans, du[V]) << endl; }

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

commuter_pass.cpp: In function 'void Dij(long long int, long long int*)':
commuter_pass.cpp:19:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(long long i = 0; i < v[x].size(); i++){
                              ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void specDIJ()':
commuter_pass.cpp:40:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(long long i = 0; i < v[x].size(); i++){
                              ~~^~~~~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...