POJ 2387

题意

有T条路, n个节点, 求从1->n的最短路

思路

模版题, dijkstra算法 ( 数据量大, 无负边 )
特别注意输入的时候要对重边进行处理

最短路径问题—Dijkstra算法详解

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+10;
int cost[maxn][maxn];
bool vis[maxn];
int d[maxn];
int n;

void init(){
    memset(d, INF, sizeof(d));
    memset(vis, false, sizeof(vis) );
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= n; j++ ){
            if( i == j )  cost[i][j] = 0;
            else    cost[i][j] = INF;
        }
}

void dijkstra(){
    d[1] = 0;
    for(;;){
        int v = -1;
        for( int i = 1; i <= n; i++ )
            if( !vis[i] && (v == -1 || d[i] < d[v]) )
                v = i;
        if( v == -1 ) break;
        vis[v] = true;
        for( int i = 1; i <= n; i++ )
            d[i] = min(d[i], d[v] + cost[v][i]);
    }
}

int main()
{
    int T;
    int a, b, c;
    while( ~scanf("%d%d",&T, &n) ){
        init();
        while( T-- ){
            scanf("%d%d%d",&a, &b, &c);
            if( c < cost[a][b] && c < cost[b][a] ){ //重边
                cost[a][b] = c;
                cost[b][a] = c;
            }
        }
        dijkstra();
        printf("%d
",d[n]);
    }
    return 0;
}