# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
395304 | 2021-04-28T06:19:36 Z | jansenkenpegrasio | Cities (BOI16_cities) | C++14 | 280 ms | 16428 KB |
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; int main() { int n,k,m; scanf("%d%d%d",&n,&k,&m); int important[k+5]; vector< pair< int,int > > adjLis[n+5]; for(int i=1;i<=k;i++) scanf("%d",& important[i]); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); adjLis[a].push_back(make_pair(b,c)); adjLis[b].push_back(make_pair(a,c)); } if(k==2) { priority_queue< pair<long long,int> >djikstra; long long distance[n+5]; fill(distance,distance+n+5,100000000000000); distance[important[1]]=0; djikstra.push(make_pair(0,important[1])); while(djikstra.empty()==false) { long long jarak = -djikstra.top().first; int asal = djikstra.top().second; djikstra.pop(); if(distance[asal]!=jarak) continue; for(int x=0;x<adjLis[asal].size();x++) { int tujuan = adjLis[asal][x].first; long long biaya = jarak + adjLis[asal][x].second; if(distance[tujuan]>biaya) { djikstra.push(make_pair(-biaya,tujuan)); distance[tujuan]=biaya; } } } printf("%lld",distance[important[2]]); } else if(k==3) { /* int terdekat; for(int a=0;a<adjLis[important[1]].size();a++) for(int b=0;b<adjLis[important[2]].size();b++) for(int c=0;c<adjLis[important[3]].size();c++) if(adjLis[important[1]][a].first==adjLis[important[2]][b].first && adjLis[important[2]][b].first==adjLis[important[3]][c].first) terdekat = adjLis[important[1]][a].first; */ // long long total=0; priority_queue< pair<long long,int> >djikstra; long long distance1[n+5]; fill(distance1,distance1+n+5,100000000000000); distance1[important[1]]=0; djikstra.push(make_pair(0,important[1])); while(djikstra.empty()==false) { long long jarak = -djikstra.top().first; int asal = djikstra.top().second; djikstra.pop(); if(distance1[asal]!=jarak) continue; for(int x=0;x<adjLis[asal].size();x++) { int tujuan = adjLis[asal][x].first; long long biaya = jarak + adjLis[asal][x].second; if(distance1[tujuan]>biaya) { djikstra.push(make_pair(-biaya,tujuan)); distance1[tujuan]=biaya; } } } // total=total+distance[terdekat]; long long distance2[n+5]; fill(distance2,distance2+n+5,100000000000000); // distance2[terdekat]=0; distance2[important[2]]=0; djikstra.push(make_pair(0,important[2])); while(djikstra.empty()==false) { long long jarak = -djikstra.top().first; int asal = djikstra.top().second; djikstra.pop(); if(distance2[asal]!=jarak) continue; for(int x=0;x<adjLis[asal].size();x++) { int tujuan = adjLis[asal][x].first; long long biaya = jarak + adjLis[asal][x].second; if(distance2[tujuan]>biaya) { djikstra.push(make_pair(-biaya,tujuan)); distance2[tujuan]=biaya; } } } // total=total+distance[terdekat]; // distance[terdekat]=0; long long distance3[n+5]; fill(distance3,distance3+n+5,100000000000000); distance3[important[3]]=0; djikstra.push(make_pair(0,important[3])); while(djikstra.empty()==false) { long long jarak = -djikstra.top().first; int asal = djikstra.top().second; djikstra.pop(); if(distance3[asal]!=jarak) continue; for(int x=0;x<adjLis[asal].size();x++) { int tujuan = adjLis[asal][x].first; long long biaya = jarak + adjLis[asal][x].second; if(distance3[tujuan]>biaya) { djikstra.push(make_pair(-biaya,tujuan)); distance3[tujuan]=biaya; } } } // total=total+distance[terdekat]; // printf("%lld\n",total); long long minimum = 1000000000000000; /* printf("Isi distance[1]\n"); for(int a=1;a<=n;a++) printf("%lld ", distance1[a]); printf("\n"); printf("Isi distance[2]\n"); for(int a=1;a<=n;a++) printf("%lld ", distance2[a]); printf("\n"); printf("Isi distance[3]\n"); for(int a=1;a<=n;a++) printf("%lld ", distance3[a]); printf("\n"); */ for(int a=1;a<=n;a++) if(distance1[a]>0 && distance2[a]>0 && distance3[a]>0) minimum = min(minimum, distance1[a]+distance2[a]+distance3[a]); printf("%lld",minimum); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Incorrect | 1 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 259 ms | 16324 KB | Output is correct |
2 | Correct | 280 ms | 16428 KB | Output is correct |
3 | Correct | 134 ms | 10172 KB | Output is correct |
4 | Correct | 78 ms | 8436 KB | Output is correct |
5 | Correct | 171 ms | 14908 KB | Output is correct |
6 | Correct | 86 ms | 8308 KB | Output is correct |
7 | Correct | 2 ms | 332 KB | Output is correct |
8 | Correct | 2 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 137 ms | 13044 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 139 ms | 12952 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |