Submission #395304

#TimeUsernameProblemLanguageResultExecution timeMemory
395304jansenkenpegrasioCities (BOI16_cities)C++14
14 / 100
280 ms16428 KiB
#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 (stderr)

cities.cpp: In function 'int main()':
cities.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:119:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |  scanf("%d%d%d",&n,&k,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
cities.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   scanf("%d",& important[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
cities.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...