三周"/>
hiho第二十三周
最短路之Dijkstra算法代码如下:
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define maxn 1010
using namespace std;
int d[maxn], w[maxn][maxn];
bool v[maxn];
int main()
{int n, m, s, t, x, y, z;scanf( "%d%d%d%d", &n, &m, &s, &t);memset( w, 0x7f, sizeof( w));for ( int i = 1; i <= n; i++)w[i][i] = 0;while ( m--){scanf( "%d%d%d", &x, &y, &z);w[x][y] = w[y][x] = min( w[x][y], z);}for ( int i = 1; i <= n; i++){d[i] = INF;}d[s] = 0;memset( v, 0, sizeof( v));for ( int i = 1; i <= n; i++){int x, m = INF;for ( int j = 1; j <= n; j++) if ( !v[j] && d[j] <= m) m = d[x = j];v[x] = 1;for ( int j = 1; j <= n; j++) d[j] = min( d[j], d[x] + w[x][j]);}printf( "%d\n", d[t]);return 0;
}
更多推荐
hiho第二十三周
发布评论