fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. inline int scan(){
  4.     char c = getchar_unlocked();
  5.     int x = 0;
  6.     while(c<'0'||c>'9'){
  7.         c=getchar_unlocked();
  8.     }
  9.     while(c>='0'&&c<='9'){
  10.         x=(x<<1)+(x<<3)+c-'0';
  11.         c=getchar_unlocked();
  12.     }
  13.     return x;
  14. }
  15. #define author rajat1603
  16. #define mod 1000000007
  17. #define pb push_back
  18. #define mp make_pair
  19. #define N 201
  20. #define inf INT_MAX-2
  21. vector<pair<int,int> > v[N];
  22. priority_queue<pair<int,int> > q;
  23. int PREV[N];
  24. int dist[N];
  25. vector<pair<int,int> > lolgraph[N];
  26. int original[N];
  27. int PREW[N];
  28. int main(){
  29.     memset(original,-1,sizeof(original));
  30.     int n=scan(),m=scan();
  31.     while(m--){
  32.         int a=scan(),b=scan(),c=scan();
  33.         v[a].pb(mp(b,c));
  34.         v[b].pb(mp(a,c));
  35.     }
  36.     int ans=1;
  37.     int ansdist=inf;
  38.     for(int i=1;i<=n;i++){
  39.         for(int j=1;j<=n;j++){
  40.             dist[j]=inf;
  41.             PREV[j]=-1;
  42.             lolgraph[j].clear();
  43.             PREW[j]=-1;
  44.         }
  45.         dist[i]=0;
  46.         q.push(mp(0,i));
  47.         while(!q.empty()){
  48.             int node=q.top().second;
  49.             q.pop();
  50.             int x=v[node].size();
  51.             while(x--){
  52.                 int next=v[node][x].first;
  53.                 int weight=v[node][x].second;
  54.                 if(dist[next]>dist[node]+weight){
  55.                     dist[next]=dist[node]+weight;
  56.                     q.push(mp(-dist[next],next));
  57.                     PREV[next]=node;
  58.                     PREW[next]=weight;
  59.                 }
  60.             }
  61.         }
  62.         bool b=0;
  63.         for(int j=1;j<=n;j++){
  64.             if(dist[j]==inf){
  65.                 b=1;
  66.                 break;
  67.             }
  68.             if(PREV[j]!=-1){
  69.                 lolgraph[PREV[j]].pb(mp(j,PREW[j]));
  70.                 lolgraph[j].pb(mp(PREV[j],PREW[j]));
  71.             }
  72.         }
  73.         if(b)continue;
  74.         int maxdistnode=i;
  75.         queue<int> bfs;
  76.         bfs.push(i);
  77.         int tempdist[N]={0};
  78.         bool visited[N]={0};
  79.         while(!bfs.empty()){
  80.             int node=bfs.front();
  81.             if(tempdist[node]>tempdist[maxdistnode]){
  82.                 maxdistnode=node;
  83.             }
  84.             visited[node]=1;
  85.             bfs.pop();
  86.             int x=lolgraph[node].size();
  87.             while(x--){
  88.                 int next=lolgraph[node][x].first;
  89.                 int weight=lolgraph[node][x].second;
  90.                 if(next!=node){
  91.                 	if(!visited[next]){
  92.                         bfs.push(next);
  93.                         tempdist[next]=tempdist[node]+weight;
  94.                 	}
  95.                 }
  96.             }
  97.         }
  98.         bool vis[N]={0};
  99.         int tempd[N]={0};
  100.         bfs.push(maxdistnode);
  101.         int maximum=0;
  102.         while(!bfs.empty()){
  103.             int node=bfs.front();
  104.             maximum=max(maximum,tempd[node]);
  105.             bfs.pop();
  106.             vis[node]=1;
  107.             int x=lolgraph[node].size();
  108.             while(x--){
  109.                 int next=lolgraph[node][x].first;
  110.                 int weight=lolgraph[node][x].second;
  111.                 if(next!=node){
  112.                 	if(!vis[next]){
  113.                         bfs.push(next);
  114.                         tempd[next]=tempd[node]+weight;
  115.                 	}
  116.                 }
  117.             }
  118.         }
  119.         if(maximum<ansdist){
  120.             ansdist=maximum;
  121.             for(int j=1;j<=n;j++){
  122.                 original[j]=PREV[j];
  123.             }
  124.         }
  125.     }
  126.     printf("%d\n",ansdist);
  127.     for(int i=1;i<=n;i++){
  128.         if(original[i]!=-1){
  129.             printf("%d %d\n",original[i],i);
  130.         }
  131.     }
  132. }
  133.  
  134.  
Success #stdin #stdout 0s 3292KB
comments (?)
stdin
copy 
6 8
2 1 2
3 1 10
4 1 20
3 2  2
4 2 18
3 4 2
4 6 10000
6 5 10000
stdout
copy 
20006
1 2
2 3
3 4
6 5
4 6
https://ideone.com/YDRLYF
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!