Untitled

mail@pastecode.io avatar
unknown
c_cpp
10 months ago
1.5 kB
5
Indexable
Never
#include <iostream>
#include <iomanip>
using namespace std;

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

void dijsktra(int s, int e) {
    for(int i = 0; i < n; i++) { // clear variable
        dist[i][i] = 0;
        vis[i] = 0;
        p[i] = 0;   
    }

    for(int i = 0; i < n; i++) {
        if(dist[s][i] != 0)
            p[i] = dist[s][i];
    }
    vis[s] = 1;

    for(int i = 0; i < n; i++) {
        
        int u = -1;
        for(int j = 0; j < n; j++) { // choose node
            if(vis[j] == 0 && u == -1)
                u = j;
            else if(vis[j] == 0 && p[j] > p[u])
                u = j;
        }
        vis[u] = 1;

        for(int j = 0; j < n; j++) {
            p[j] = max(p[j], p[u] * dist[u][j]);
        }
    }
}

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) << p[e] << endl;
    }
}
Leave a Comment