Untitled

mail@pastecode.io avatar
unknown
c_cpp
6 months ago
876 B
3
Indexable
Never
#include <iostream>
#include <iomanip>
using namespace std;
#define INF -1e9

int n, m, r;
int vis[505];
double p[505];
double dist[505][505];

void floyd() {
    for(int i = 0; i < n; i++) 
        dist[i][i] = 0;
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dist[i][j] = max(dist[i][j], dist[i][k] * dist[k][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m >> r;
    for(int i = 0; i < m; i++) {
        int a, b;
        double pb;
        cin >> a >> b >> pb;
        dist[a][b] = pb;
        dist[b][a] = pb;
    }
    floyd();
    for(int i = 0; i < r; i++) {
        int s, e;
        cin >> s >> e;
        // dijsktra(s, e);
        if(s == e)
            cout << "1.00000\n";
        else
            cout << fixed << setprecision(5) << dist[s][e] << endl;
    }
}
Leave a Comment