Submission #649669

#TimeUsernameProblemLanguageResultExecution timeMemory
649669UzoufCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
109 ms262144 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); int cost[n+5][n+5]; for (int i=0;i<=n;i++) { for (int j=0;j<=n;j++) cost[i][j]=1e18; cost[i][i]=0; } 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}); cost[a][b]=c; cost[b][a]=c; } int dis[n+5],par[n+5]; for (int i=0;i<=n;i++) { dis[i]=1e18; par[i]=i; } priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; q.push({0,s}); dis[s]=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=cost[i][ii]; int nwc=c+cc; if (dis[ii]>nwc) { dis[ii]=nwc; q.push({nwc,ii}); par[ii]=i; } } } int indx=t; while (indx!=s) { cost[indx][par[indx]]=0; cost[par[indx]][indx]=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=cost[i][ii]; int nwc=c+cc; if (dis[ii]>nwc) { dis[ii]=nwc; q.push({nwc,ii}); par[ii]=i; } } } cout<<dis[v]; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:36: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]
   36 |         for (int j=0;j<vv[i].size();j++) {
      |                      ~^~~~~~~~~~~~~
commuter_pass.cpp:61: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]
   61 |         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...