题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2544

解题思路

Dijkstra算法
典型例题讲解

AC代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=0x3f3f3f3f;
const int N=110;
int n,m;
struct edge{
    int to,cost;
};
vector<edge> G[N];
int dis[N];
typedef pair<int,int> P;
void Dijkstra(){
    priority_queue<P, vector<P>, greater<P> > q;
    q.push(P(0,1));
    dis[1]=0;
    while(!q.empty()){
        P p=q.top();q.pop();
        int v=p.second;
        if(dis[v]!=p.first) continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(dis[e.to]>dis[v]+e.cost){
                dis[e.to]=dis[v]+e.cost;    
                q.push(P(dis[e.to],e.to));
            }
        }
    }
}
void init(){//注意对每组数据操作前都要初始化
    fill(dis,dis+n+1,INF);
    for(int i=1;i<=n;i++)
        G[i].clear();
    fill(dis,dis+n+1,INF);
}
int main(){

    while((cin>>n>>m)&&n&&m){
        init();
        for(int i=1;i<=m;i++){
            int from,to,cost;
            cin>>from>>to>>cost;
            edge tmp;
            tmp.to=to;tmp.cost=cost;
            G[from].pb(tmp);
            tmp.to=from;
            G[to].pb(tmp);
        }

        Dijkstra();
        cout<<dis[n]<<endl;
    }
}