제출 #649680

#제출 시각아이디문제언어결과실행 시간메모리
649680UzoufCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
272 ms16900 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; int s,t,u,v; cin>>s>>t>>u>>v; vector<vector<pair<int,int> > > vv(n+5); for (int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; vv[a].push_back({b,c}); vv[b].push_back({a,c}); } int dis[n+5],par[n+5]; for (int i=0;i<=n;i++) { dis[i]=1e18; par[i]=-1; } priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; q.push({0,s}); dis[s]=0; par[s]=s; while (!q.empty()) { int c=q.top().first,i=q.top().second; q.pop(); if (c>dis[i]) continue; for (int j=0;j<vv[i].size();j++) { int ii=vv[i][j].first,cc=vv[i][j].second; int nwc=c+cc; if (dis[ii]>nwc) { dis[ii]=nwc; q.push({nwc,ii}); par[ii]=i; } } } int indx=t; while (indx!=s) { for (int i=0;i<vv[indx].size();i++) { if (vv[indx][i].first==par[indx]) vv[indx][i].second=0; } for (int i=0;i<vv[par[indx]].size();i++) { if (vv[par[indx]][i].first==indx) vv[par[indx]][i].second=0; } indx=par[indx]; } for (int i=0;i<=n;i++) dis[i]=1e18; q.push({0,u}); dis[u]=0; while (!q.empty()) { int c=q.top().first,i=q.top().second; q.pop(); if (c>dis[i]) continue; for (int j=0;j<vv[i].size();j++) { int ii=vv[i][j].first,cc=vv[i][j].second; int nwc=c+cc; if (dis[ii]>nwc) { dis[ii]=nwc; q.push({nwc,ii}); par[ii]=i; } } } cout<<dis[v]; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:29:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j=0;j<vv[i].size();j++) {
      |                      ~^~~~~~~~~~~~~
commuter_pass.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i=0;i<vv[indx].size();i++) {
      |                      ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:45:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i=0;i<vv[par[indx]].size();i++) {
      |                      ~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j=0;j<vv[i].size();j++) {
      |                      ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...