제출 #853692

#제출 시각아이디문제언어결과실행 시간메모리
853692lftroqCommuter Pass (JOI18_commuter_pass)C++14
24 / 100
402 ms49676 KiB
/* , ,. | \ |: \ ; :\ :' ;\| ::\ \ : | `::\ _) | `:`. ,' , `. ;: ; ,' ;: ;"' ,:: |_ /, ` . ;::: |:`-.__ _,' _o\ ,::.`:' ; ; . ' _,-' `:. ;""\, ,-' ,: `-;, \, ;: ;--._ `.______,-,----._ ,' ;: ,/ , ,` / /,-';' \ ; `: ,'/,::.::: ,',;-'-'_,--; ; :. ,',',;:::::: ( /___,-' `. ;::,,'o/ ,::::::: `' ) ;:,'o / ;"- -:: \__ _,'o ,' ,:: ) `--' ,..:::: _lftroq_ ; `. ,::::::: ; ``::. ::::::: */ #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MOD 1000000007LL #define MOD2 998244353LL #define endl '\n' #define INFINITE 2147483647LL #define INFINITE2 9223372036854775807 #define llll pair<ll,ll> #define ldld pair<ld,ld> #define fi first #define se second typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; vector<llll> graph[400005]; ll u[200005],v[200005],w[200005],d[100005],d1[100005]; void dijkstra(ll s) { memset(d,0x3f,sizeof(d)); priority_queue<llll,vector<llll>,greater<llll>> pq; d[s]=0; pq.push({d[s],s}); while(pq.size()) { ll u=pq.top().se; pq.pop(); for(int i=0;i<graph[u].size();i++) { ll v=graph[u][i].fi,w=graph[u][i].se; if(d[v]>d[u]+w) { d[v]=d[u]+w; pq.push({d[v],v}); } } } } void dijkstra1(ll s) { memset(d1,0x3f,sizeof(d1)); priority_queue<llll,vector<llll>,greater<llll>> pq; d1[s]=0; pq.push({d1[s],s}); while(pq.size()) { ll u=pq.top().se; pq.pop(); for(int i=0;i<graph[u].size();i++) { ll v=graph[u][i].fi,w=graph[u][i].se; if(d1[v]>d1[u]+w) { d1[v]=d1[u]+w; pq.push({d1[v],v}); } } } } void solve() { ll n,m,s,t,x,y; cin >> n >> m >> s >> t >> x >> y; s--;t--;x--;y--; for(int i=1;i<=m;i++) { cin >> u[i] >> v[i] >> w[i]; u[i]--;v[i]--; graph[u[i]].push_back({v[i],w[i]}); graph[v[i]].push_back({u[i],w[i]}); graph[3*n+u[i]].push_back({3*n+v[i],w[i]}); graph[3*n+v[i]].push_back({3*n+u[i],w[i]}); } dijkstra(s); dijkstra1(t); for(int i=1;i<=m;i++) { if(d[u[i]]+w[i]+d1[v[i]]==d[t]) { graph[n+u[i]].push_back({n+v[i],0}); graph[2*n+v[i]].push_back({2*n+u[i],0}); } else if(d[v[i]]+w[i]+d1[u[i]]==d[t]) { graph[2*n+u[i]].push_back({2*n+v[i],0}); graph[n+v[i]].push_back({n+u[i],0}); } } for(int i=0;i<n;i++) { graph[i].push_back({n+i,0}); graph[i].push_back({2*n+i,0}); graph[n+i].push_back({3*n+i,0}); graph[2*n+i].push_back({3*n+i,0}); } dijkstra(x); cout << d[3*n+y] << endl; } int main() { fastIO //freopen("hanhhhh.inp","r",stdin); //freopen("hanhhhh.out","w",stdout); ll t=1; //cin >> t; while(t--) solve(); return 0; }

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

commuter_pass.cpp: In function 'void dijkstra(ll)':
commuter_pass.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(ll)':
commuter_pass.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...