Skip to content

14198: 【原4198】反败为胜

题目

题目描述

author: 失败 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4198

题目描述

失败的阴霾覆盖了整个世界。此时的人类为了躲避失败阴霾,只能躲藏在几个分散的据点之中。为了拯救这个世界,人类要使用成功之光驱散失败阴霾。

“让大家看不到失败,让成功永远在。”——《祈祷》

终于,有人点燃了成功火炬,发出了成功之光。成功之光可以沿成功光路从一个据点传播到另外一个据点,当然这需要一些时间。

请编写一个程序,计算成功之光照亮全世界所花费的时间。

输入格式

第一行是两个正整数N和M,表示据点数量和成功光路数量。 接下去M行,每行三个数字u,v,w,表示从据点u到据点v有一条需要耗时w的成功光路。

据点编号从1开始。成功火炬位于编号为1的据点。

输出格式

输出一个整数,表示成功之光照亮全世界所花费的时间。如果最终成功之光没有能够照亮全世界,请输出-1。

样例输入

5 9
2 5 10
1 5 10
2 3 35
3 5 55
4 5 24
1 3 38
3 4 32
1 4 72
2 4 85

样例输出

38

数据规模

对于30%的数据,\(1 \le N \le 100 \)。

对于100%的数据,\(1 \le N \le 5000 , 1 \le M \le 500N \)。

所有数据均在int范围内。

Hint

费马原理:光线传播的路径是需时最少的路径。

光路可逆。

zqy2018's solution

/*
    Hint: use Dijkstra's algorithm
*/
#include <bits/stdc++.h>
#define INF 1000000000000000ll
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
struct Edge{
    int v, cost, nxt;
};
Edge e[5000005];
int at[5005] = {0}, cnt = 0;
ll d[5005];
bool vis[5005] = {0};
int V, E;
void addEdge(int u, int v, int c){
    e[++cnt].v = v, e[cnt].cost = c, e[cnt].nxt = at[u], at[u] = cnt;
}
void dijkstra(){
    for(int i = 1; i <= V; ++i)
        d[i] = INF;
    d[1] = 0;
    for(int i = 1; i <= V; ++i){
        ll mind = INF;
        int minp = -1;
        for(int j = 1; j <= V; ++j)
            if(mind > d[j] && !vis[j])
                mind = d[j], minp = j;
        vis[minp] = true;
        for(int j = at[minp]; j; j = e[j].nxt)
            d[e[j].v] = min(d[e[j].v], d[minp] + 1ll * e[j].cost);
    }
}
void init(){
    scanf("%d", &V);
    int E = read();
    for(int i = 1; i <= E; ++i){
        int u_ = read(), v_ = read(), c_ = read();
        addEdge(u_, v_, c_), addEdge(v_, u_, c_);
    }
}
void solve(){
    dijkstra();
    ll ans = 0;
    for(int i = 1; i <= V; ++i){
        if(d[i] == INF){
            ans = -1; 
            break;
        }else{
            ans = max(ans, d[i]);
        }       
    }
    if(ans < 0) printf("-1\n");
    else printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}