【POJ - 3268 】Silver Cow Party （最短路 Dijkstra算法）

Silver Cow Party

Descriptions

给出n个点和m条边，接着是m条边，代表从牛a到牛b需要花费c时间，现在所有牛要到牛x那里去参加聚会，并且所有牛参加聚会后还要回来，给你牛x，除了牛x之外的牛，他们都有一个参加聚会并且回来的最短时间，从这些最短时间里找出一个最大值输出

Input

第1行：三个空格分隔的整数，分别为： N， M和 X
行2 .. M +1：行 i +1描述具有三个空格分隔整数的道路 i： A _i， B _i和 T _i。所描述的道路从农场A _i运行到农场 B _i，需要 T _i个时间单位来遍历。

Output

第1行：一个整数：所有奶牛最短路径中的最大值。

Sample Input

Sample Output

Hint

奶牛4直接进入该聚会（3个单位），并通过1号和3号农场（7个单位）返回，总共10个时间单位。 题目链接 https://vjudge.net/problem/POJ-3268 1000³用Floyd算法会超时，用Dijkstra算法，稍微改一下即可 AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>1
#include 
#include 
#include 
#include <set>
#include 
#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 1000+5
#define P pair//first最短路径second顶点编号
using namespace std;
int N,M,X;
struct edge
{
    int to,cost;
    edge(int to,int cost):to(to),cost(cost){}
};
vectorG[Maxn];//G[i] 从i到G[i].to的距离为cost
int d[Maxn][Maxn];//d[i][j]从i到j的最短距离
void Dijk(int s)
{
    priority_queue,greater >q;//按first从小到大出队
    for(int i=0;i<=N;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)
        {
            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;
    cin>>N>>M>>X;
    for(int i=0; i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        G[x].push_back(edge(y,z));
    }
    for(int i=1;i<=N;i++)//枚举所有两点间的最短距离
        Dijk(i);
    int ans=0;
    for(int i=1;i<=N;i++)
    {
        if(i==X)
            continue;
        ans=max(ans,d[i][X]+d[X][i]);
    }
    cout<endl;
    return 0;
}

【POJ】题解图论——最短路

【POJ - 3268 】Silver Cow Party （最短路 Dijkstra算法）

Silver Cow Party

相关

标签