codeforces DIV2 D 最短路

http://codeforces.com/contest/716/problem/D

题目大意：给你一些边，有权值，权值为0的表示目前该边不存在，但是可以把0修改成另外一个权值。现在，我们重新建路，问让s-t的最短路能否刚好是L？

思路：暴力修改即可。。。

//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha
")
const int maxn = 1000 + 5;
const LL inf = 1e17;
struct Edge{
    int from, to; LL val;
    Edge(int u = 0, int v = 0, LL val = 0): from(u), to(v), val(val){}
};
vector<Edge> G[maxn];
vector<Edge> zero;
vector<Edge> realroad;
int n, m, s, t;
LL L;
LL d[maxn];

void dijstra(int s){
    queue<int> que;
    for (int i = 0; i < n; i++) d[i] = inf;
    que.push(s);
    d[s] = 0;
    while (!que.empty()){
        int u = que.front(); que.pop();
        int len = G[u].size();
        for (int i = 0; i < len; i++){
            Edge &e = G[u][i];
            if (d[e.to] > d[u] + e.val){
                d[e.to] = d[u] + e.val;
                que.push(e.to);
            }
        }
    }
}

int main(){
    cin >> n >> m >> L >> s >> t;
    for (int i = 0; i < m; i++){
        int u, v; LL val; scanf("%d%d%I64d", &u, &v, &val);
        if (val != 0) {
            G[u].push_back(Edge(u, v, val)), G[v].push_back(Edge(v, u, val));
            realroad.push_back(Edge(u, v, val));
        }
        else if (val == 0) zero.push_back(Edge(u, v, val));
    }
    dijstra(s);
    ///printf("d[t] = %I64d
", d[t]);
    if (d[t] < L) {
        printf("NO
"); return 0;
    }
    else if (d[t] == L){
        printf("YES
");
        for (int i = 0; i < realroad.size(); i++){
            printf("%d %d %I64d
", realroad[i].from, realroad[i].to, realroad[i].val);
        }
        for (int i = 0; i < zero.size(); i++){
            printf("%d %d %I64d
", zero[i].from, zero[i].to, inf);
        }
        return 0;
    }

    for (int i = 0; i < zero.size(); i++){
        Edge &e = zero[i];
        G[e.from].push_back(Edge(e.from, e.to, 1));
        G[e.to].push_back(Edge(e.to, e.from, 1));
        e.val = 1;
        dijstra(s);
        if (d[t] <= L){
            e.val = L - d[t] + 1;
            break;
        }
    }
    if (d[t] > L) printf("NO
");
    else {
        printf("YES
");
        for (int i = 0; i < realroad.size(); i++){
            printf("%d %d %I64d
", realroad[i].from, realroad[i].to, realroad[i].val);
        }
        for (int i = 0; i < zero.size(); i++){
            if (zero[i].val == 0)printf("%d %d %I64d
", zero[i].from, zero[i].to, inf);
            else printf("%d %d %I64d
", zero[i].from, zero[i].to, zero[i].val);
        }
    }

    return 0;
}

/看看会不会爆int!数组会不会少了一维！//取物问题一定要小心先手胜利的条件#include<bits/stdc++.h>usingnamespace std;#define LL longlong#define ALL(a) a.begin(), a.end()#define pb push_back
#define mk make_pair
#definefi first
#define se second
#define haha printf("haha
")constint maxn =1000+5;const LL inf =1e17;structEdge{intfrom, to; LL val;Edge(int u =0,int v =0, LL val =0):from(u), to(v), val(val){}};
vector<Edge> G[maxn];
vector<Edge> zero;
vector<Edge> realroad;int n, m, s, t;
LL L;
LL d[maxn];void dijstra(int s){
    queue<int> que;for(int i =0; i < n; i++) d[i]= inf;
    que.push(s);
    d[s]=0;while(!que.empty()){int u = que.front(); que.pop();int len = G[u].size();for(int i =0; i < len; i++){Edge&e = G[u][i];if(d[e.to]> d[u]+ e.val){
                d[e.to]= d[u]+ e.val;
                que.push(e.to);}}}}int main(){
    cin >> n >> m >> L >> s >> t;for(int i =0; i < m; i++){int u, v; LL val; scanf("%d%d%I64d",&u,&v,&val);if(val !=0){
            G[u].push_back(Edge(u, v, val)), G[v].push_back(Edge(v, u, val));
            realroad.push_back(Edge(u, v, val));}elseif(val ==0) zero.push_back(Edge(u, v, val));}
    dijstra(s);///printf("d[t] = %I64d
", d[t]);if(d[t]< L){
        printf("NO
");return0;}elseif(d[t]== L){
        printf("YES
");for(int i =0; i < realroad.size(); i++){
            printf("%d %d %I64d
", realroad[i].from, realroad[i].to, realroad[i].val);}for(int i =0; i < zero.size(); i++){
            printf("%d %d %I64d
", zero[i].from, zero[i].to, inf);}return0;}for(int i =0; i < zero.size(); i++){Edge&e = zero[i];
        G[e.from].push_back(Edge(e.from, e.to,1));
        G[e.to].push_back(Edge(e.to, e.from,1));
        e.val =1;
        dijstra(s);if(d[t]<= L){
            e.val = L - d[t]+1;break;}}if(d[t]> L) printf("NO
");else{
        printf("YES
");for(int i =0; i < realroad.size(); i++){
            printf("%d %d %I64d
", realroad[i].from, realroad[i].to, realroad[i].val);}for(int i =0; i < zero.size(); i++){if(zero[i].val ==0)printf("%d %d %I64d
", zero[i].from, zero[i].to, inf);else printf("%d %d %I64d
", zero[i].from, zero[i].to, zero[i].val);}}return0;}