Untitled
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