即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

1126 – 咸鱼旅行(最大路径最小值)

编程语言 qq_34287501 25℃ 0评论

题目链接:http://www.ifrog.cc/acm/problem/1126

1126 – 咸鱼旅行

Time Limit:3s Memory Limit:128MByte

Submissions:580Solved:110

DESCRIPTION

这个地区可以看作是一个无向图,N个点M条边组成。每个边有一个边权。我们定义一条路径的花费,就是这条路径上最大的边权。


现在有一条咸鱼,想从S走到T,徒步旅行。


咸鱼于是找到了你,想让你告诉他从S到T的最小花费。

INPUT
第一行两个整数,N,M。满足(1 <= N <= 10^5, 0 <= M <= 5*10^5)接下来M行,每行三个整数U,V,C。表示有一个连接U点和V点的边,且边权是C。(1<=C<=10^9)接下来一个行是两个整数S,T(1<=S,T<=n)
OUTPUT
输出答案,如果S不能到达T,输出-1
SAMPLE INPUT
5 5
1 2 1
2 3 1
3 4 1
4 5 1
5 1 1
1 3
SAMPLE OUTPUT
1


解析:最短路问题,最大路径最小值,吃两次亏了,一次是2017-3-19 CCF D题写错成有向图(再加一条路径变成无向图就能得100分,结果20分),另外一次就是2017-5-27 蓝桥杯国赛第四题判断有无环,输出环所在的节点(又是硬生生的给写成有向图),这次玲珑杯河南专场,就算所有题都不写,也要过这个题,真是气人


代码:

#include
#define N 100009
using namespace std;

struct node
{
    int v, w;
};

vector T[N];

typedef pair P;

inline void q_read(int &num)
{
    int f = 1; char ch;
    while(true)
    {
        ch = getchar();
        if(ch == '-') f = -1;
        if(isdigit(ch))
        {
            num = ch - '0';
            break;
        }
    }
    while(ch = getchar(), isdigit(ch)) num = num * 10 + ch - '0';
    num *= f;
}


int solve(int n, int S, int TT)
{
    int d[N];
    memset(d, 0x3f, sizeof(d));
    priority_queue, greater

> q; d[S] = 0; q.push(P(0, S)); while(!q.empty()) { P p = q.top(); q.pop(); int v = p.second; if(d[v] < p.first) continue; for(int i = 0; i < T[v].size(); i++) { node &e = T[v][i]; if(d[e.v] == 0x3f3f3f3f || d[e.v] > max(d[v], e.w)) { d[e.v] = max(d[v], e.w); q.push(P(d[e.v], e.v)); } } } return d[TT] == 0x3f3f3f3f ? -1: d[TT]; } int main() { int n, m, u, v, w, S, TT; q_read(n); q_read(m); for(int i = 1; i <= m; i++) { //scanf("%d%d%d", &u, &v, &w); q_read(u); q_read(v); q_read(w); T[u].push_back((node){v, w}); T[v].push_back((node){u, w}); } //scanf("%d%d", &S, &TT); q_read(S); q_read(TT); int ans = solve(n, S, TT); printf("%d\n", ans); return 0; }






转载请注明:CodingBlog » 1126 – 咸鱼旅行(最大路径最小值)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情