【POJ - 2387】Til the Cows Come Home（最短路径 Dijkstra算法）

佚名 5年前 (2019-08-14) 算法 1088人围观抢沙发百度已收录

Til the Cows Come Home

大奶牛很热爱加班，他和朋友在凌晨一点吃完海底捞后又一个人回公司加班，为了多加班他希望可以找最短的距离回到公司。
深圳市里有N个(2 <= N <= 1000)个公交站，编号分别为1..N。深圳是大城市，公交车整天跑跑跑。公交站1是大奶牛的位置,公司所在的位置是N。所有公交站中共有T (1 <= T <= 2000)条双向通道。大奶牛对自己的导航能力不太自信，所以一旦开始，他总是沿着一条路线走到底。
大奶牛为了锻炼未来的ACMer，决定让你帮他计算他到公司的最短距离。可以保证存在这样的路存在。Input第一行:两个整数:T和N
接下来T行:每一行都用三个空格分隔的整数描述一个轨迹。前两个整数是路线经过的公交站台。第三个整数是路径的长度，范围为1到100。Output一个整数，表示大奶牛回到公司的最小距离。

Sample Input
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90

题目链接

https://vjudge.net/problem/POJ-2387

Dijkstra模板题，不说了

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>1
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 2000+5
#define P pair<int,int>//first最短路径second顶点编号
using namespace std;
int N,M,X;
struct edge
{
    int to,cost;
    edge(int to,int cost):to(to),cost(cost) {}
};
vector<edge>G[Maxn];//G[i] 从i到G[i].to的距离为cost
int d[Maxn][Maxn];//d[i][j]从i到j的最短距离
void Dijk(int s)
{
    priority_queue<P,vector<P>,greater<P> >q;//按first从小到大出队
    for(int i=0; i<=M; i++)
        d[s][i]=INF;
    d[s][s]=0;
    q.push(P(0,s));
    while(!q.empty())
    {
        P p=q.top();
        q.pop();
        int v=p.second;//点v
        if(d[s][v]<p.first)
            continue;
        for(int i=0; i<G[v].size(); i++)
        {
            edge e=G[v][i];//枚举与v相邻的点
            if(d[s][e.to]>d[s][v]+e.cost)
            {
                d[s][e.to]=d[s][v]+e.cost;
                q.push(P(d[s][e.to],e.to));
            }
        }
    }
}
int main()
{
    IOS;
    while(cin>>N>>M)
    {
        for(int i=0; i<N; i++)
        {
            int x,y,z;
            cin>>x>>y>>z;
            G[x].push_back(edge(y,z));
            G[y].push_back(edge(x,z));
        }
        Dijk(1);
        cout<<d[1][M]<<endl;
    }
    return 0;
}