hdu 2544 单源最短路问题 dijkstra+堆优化模板

水深无声 2022-08-03 00:11 205阅读 0赞

# 最短路 #

**Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 41168    Accepted Submission(s): 17992**

Problem Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。  
输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1
    1 2 3
    3 3
    1 2 5
    2 3 5
    3 1 2
    0 0

Sample Output

3
    2

Source

[UESTC 6th Programming Contest Online ][UESTC 6th Programming Contest Online]

最短路的入门题，刚开始接触，好神奇~~

//hdu 2544 最短路
    // dijkstra堆优化模板
    //大部分参照挑战程序设计竞赛书上代码
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    struct st
    {
        int to;
        int cost;
        st(int a,int b)//构造函数
        {
            to=a;
            cost=b;
        }
    };
    
    int dis[111];
    vector<st> v[111];
    //通过指定greater<pii>参数，堆会按照first从小到大的顺序取出值
    priority_queue<pii,vector<pii>,greater<pii> > q;
                                        //pair<int,int>的first表示最短距离，second表示顶点编号
    int main()
    {
    
        int n,m;
        while(~scanf("%d%d",&n,&m) && n)
        {
            mem(dis,inf);          //初始化无穷大
            for(int i=0;i<=n;i++)
            {
                v[i].clear();
            }
            for(int i=1;i<=m;i++)
            {
                int t=in();
                int t1=in(),t2=in();
                v[t].push_back(st(t1,t2));
                v[t1].push_back(st(t,t2));//无向图必须push两次
            }
            q.push(pii(0,1));
            dis[1]=0;       //初始化
            while(!q.empty())
            {
                pii x = q.top();     
                q.pop();
                int tmp=x.second;
                if(dis[tmp]<x.first)continue;
                for(int i=0;i<(int)v[tmp].size();i++)//当前顶点能到的点
                {
                    st t=v[tmp][i];
                    if(dis[t.to]>dis[tmp]+t.cost) //当前顶点最短距离+它到这一点的距离是否比它能到的这点的最短距离小
                    {
                        dis[t.to]=dis[tmp]+t.cost;  //小的话就更新
                        q.push(pii(dis[t.to],t.to)); //并且入队
                    }
                }
            }
            cout<<dis[n]<<endl;
        }
        return 0;
    }

[UESTC 6th Programming Contest Online]: http://acm.hdu.edu.cn/search.php?field=problem&key=UESTC+6th+Programming+Contest+Online&source=1&searchmode=source