Solution of 10246 Asterix and Obelix

"All pair shortest path" বের করার সময় শুধুমাত্র path এর cost দেওয়া থাকে আর তার উপর ভিত্তি করে ans বের করতে হয়। কিন্তু এখানে শুধু path এর cost না, সাথে সেই path এর maximum node cost নিবে । অর্থাৎ two dimensional purpose। এই ক্ষেত্রে দুইবার Floyd Warshall প্রয়োগ করতে হবে। 

/* Bismillahir Rahmanir Rahim Just apply "Floyd Warshall" algorithm two times */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=ml i--) #define inf 100000000 using namespace std; int main(){ int cs=1, n, m, r, u, v, w, q, tcost; while(1){ int total, x, dis[90][90], c[90][90]; cin>>n>>m>>q; if(n==0&&m==0&&q==0) break; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(i==j) dis[i][j]=0; else dis[i][j]=inf; c[i][j]=inf; } } fi(1, n){ cin>>x; c[i][i]=x; } fi(1, m){ cin>>u>>v>>w; dis[u][v]=w; dis[v][u]=w; c[u][v]=c[v][u]=max(c[u][u], c[v][v]); } for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ total=dis[i][k]+dis[k][j]; tcost=max(c[i][k], c[k][j]); if(dis[i][j]+c[i][j]>total+tcost){ dis[i][j]=total; c[i][j]=tcost; } } } } for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ total=dis[i][k]+dis[k][j]; tcost=max(c[i][k], c[k][j]); if(dis[i][j]+c[i][j]>total+tcost){ dis[i][j]=total; c[i][j]=tcost; } } } } if(cs!=1)cout<<endl; cout<<"Case #"<<cs++<<endl; fi(1, q){ cin>>u>>v; if(dis[u][v]>=inf) cout<<-1<<endl; else cout<<dis[u][v]+c[u][v]<<endl; } } return 0; }