Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const long long INF = 1e18;
- typedef long long ll;
- int s1, t1;
- int s2, t2;
- int n, m;
- vector<vector<long long>> dp;
- int nv[201][201];
- vector<int> ans;
- int main(){
- //freopen("floydwarshall.in", "r", stdin);
- cin >> s1 >> t1;
- cin >> s2 >> t2;
- cin >> n >> m;
- dp.resize(n+1, vector<ll>(n+1, INF));
- for(int i=0; i<m; i++){
- ll a, b, c;
- cin >> a >> b >> c;
- //need to check for minimum because same routes can repeat with different values
- dp[a][b] = min(dp[a][b], c);
- dp[b][a] = min(dp[b][a], c);
- //nv[a][b] = a;
- //nv[b][a] = b;
- }
- for(int i=1; i<=n; i++){
- for(int j=1; j<=n; j++){
- nv[i][j] = j;
- nv[j][i] = i;
- }
- }
- for(int i=1; i<=n; i++){
- dp[i][i] = 0;
- }
- for(int k=1; k<=n; k++){
- for(int i=1; i<=n; i++){
- for(int j=1; j<=n; j++){
- //nv[i][j] = i;
- //need to check alll conditions including lexicographical condition within checking infinite and checking node values
- if(i != k && j != k && dp[i][k] != INF && dp[k][j] != INF){
- if(dp[i][j] > dp[i][k]+dp[k][j]){
- dp[i][j] = dp[i][k]+dp[k][j];
- nv[i][j] = nv[i][k];
- }else if(dp[i][j] == dp[i][k]+dp[k][j]){
- if(nv[i][j]>nv[i][k]){
- nv[i][j] = nv[i][k];
- }
- }
- }
- }
- }
- }
- //for(int i=1; i<=n; i++){
- //for(int j=1; j<=n; j++){
- //cout << dp[i][j] << " ";
- //}
- //cout << '\n';
- //}
- cout << dp[s1][t1] << '\n';
- int cur = s1;
- cout << s1;
- //cout << nv[cur][s1] << '\n';
- //int v = 20;
- while(cur != t1){
- cout << " " << nv[cur][t1];
- cur = nv[cur][t1];
- }
- cout << '\n';
- cout << dp[s2][t2] << '\n';
- cur = s2;
- cout << s2;
- //cout << nv[cur][s1] << '\n';
- //v = 20;
- while(cur != t2){
- cout << " " << nv[cur][t2];
- cur = nv[cur][t2];
- }
- cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
