最短路

题目链接

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;
    }
}
全部评论

相关推荐

09-30 15:27
已编辑
成都工业学院 企业文化
Morpheus_:候选人:还需要测验武力值?
投递腾讯等公司10个岗位
点赞 评论 收藏
分享
08-27 12:02
已编辑
南京外国语学校 网络安全
再来一遍:实则劝各位不要all in华子,不要相信华为hr
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务