- C++
Dijkstra
-
潘一诺 (东城提高一班潘一诺) LV 8 @ 2025-5-18 11:56:25
话说这个名字
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m, a, b, c, g[N][N], flag[N], dis[N];
int main() {
cin >> n >> m ;
memset(g, 0x3f, sizeof(g));
for(int i = 1; i <= n; i++) g[i][i] = 0;
for(int i = 1; i <= m; i++) {
cin >> a >> b >> c ;
g[a][b] = g[b][a] = c;
}
for(int i = 1; i <= n; i++) dis[i] = g[1][i];
flag[1] = 1;
for(int i = 1; i <= n; i++) {
int min_dis = 1e9, node;
for(int j = 1; j <= n; j++) {
if(!flag[j] && dis[j] < min_dis) {
node = j;
min_dis = dis[j];
}
}
flag[node] = 1;
for(int j = 1; j <= n; j++) {
if(dis[j] > dis[node] + g[node][j])
dis[j] = dis[node] + g[node][j];
}
}
cout << dis[n] ;
return 0;
}
3 条评论
-
-
`#include #include #include
using namespace std;
const int MAXN = 2005; double graph[MAXN][MAXN];
int main() { int n, m; cin >> n >> m;
// 初始化图，不可达设为0，自己到自己设为1 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i == j) graph[i][j] = 1.0; else graph[i][j] = 0.0; } } // 输入转账关系并更新图 for (int i = 0; i < m; ++i) { int x, y; double z; cin >> x >> y >> z; graph[x][y] = graph[y][x] = (100.0 - z) / 100.0; } // Floyd算法求解最大乘积路径 for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (graph[i][k] > 0 && graph[k][j] > 0) { graph[i][j] = max(graph[i][j], graph[i][k] * graph[k][j]); } } } } // 输入起点和终点 int A, B; cin >> A >> B; // 计算并输出结果 double result = 100.0 / graph[A][B]; cout << fixed << setprecision(8) << result << endl; return 0;}`
- 1
