Codeforces Round #372 (Div. 2) -- D. Complete The Graph（Dijkstra单源最短路）

大体题意：

给你一个无向图，有n 个顶点和m 个边，一些边的权重是正数，一些边的权重是0，表示已经删除，告诉你起始位置和终止位置和最短路L，要求把已经删除的边（权值为0）重建，自己赋值，使得最短路依然是L。

思路：

单源最短路，其实想清楚了还是很简单的！

先求一遍最短路，当发现最短路L2 小于L时，那么肯定是无解的，因为你此时最短路已经小于L了，在加入一些重建的边，只能会越来越小，因此不可能达到L！

如果L2 == L 我们就可以直接输出了，把0边随便输出一个inf 无穷大就好（相当于此路不通！！）

如果L2 < L的话，我们就要加0边了！

枚举每一个0边，加入一个0边就在求一次最短路，直到加入某个边使得最短路不大于L即可！把此时的位置记录下来！

那么先输出已知边，在输出记录位置的0边之前的边，权值为1，然后根据L和最短路的关系算出记录位置的0边的权重！

最后剩下的0边随意输出一个inf即可！

详细见代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define ps push_back
#define mr make_pair
using namespace std;
typedef unsigned long long ll;
//typedef unsigned long long ULL;
const ll maxn = 1000 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;
const double pi = acos(-1.0);
int g[maxn][maxn];
struct haha{
int x,y,w;
}p[maxn*10],p0[maxn*10];
struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,u;
    bool operator < (const HeapNode& rhs)const {
        return d > rhs.d;
    }
};
struct Dijkstra{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n){
        this->n = n;
        for (int i = 0; i < n; ++i) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m = edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s){
        priority_queue<HeapNode>Q;
p[s] = -1;
        for (int i = 0; i < n; ++i) d[i] = INF;
        d[s] = 0;
        memset(done,0,sizeof done);
        Q.push((HeapNode){0,s});
        while(!Q.empty()){
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if (done[u]) continue;
            done[u] = true;
            for (int i = 0; i < G[u].size(); ++i){
                Edge & e = edges[G[u][i]];
                if (d[e.to] > d[u] + e.dist){
                    d[e.to] = d[u] + e.dist;
                    p[e.to] = e.from;
                    Q.push((HeapNode){d[e.to],e.to});
                }

            }

        }
    }
}dij;

int main(){
int n,m,L,s,t;
int cnt = 0,cnt2 = 0;
scanf("%d %d %d %d %d",&n,&m, &L, &s, &t);
dij.init(n);
for (int i = 0; i < m; ++i){
int u,v,w;
scanf("%d %d %d",&u,&v, &w);
g[u][v] = g[v][u] = w;
if (w){
p[cnt].x = u;
p[cnt].w = w;
p[cnt++].y = v;
dij.AddEdge(u,v,w);
dij.AddEdge(v,u,w);
}
else {
p0[cnt2].x = u;
p0[cnt2].w = 0;
p0[cnt2++].y = v;
}
}
dij.dijkstra(s);
//printf("dt = %d\n",dij.d[t]);
if (dij.d[t] < L) return 0 * puts("NO");
if (dij.d[t] == L){
puts("YES");
for (int i = 0; i < cnt; ++i){
printf("%d %d %d\n",p[i].x,p[i].y,p[i].w);
}
for (int i = 0; i < cnt2; ++i){
printf("%d %d %d\n",p0[i].x,p0[i].y,INF);
}
return 0;
}
int pos = -1;
for (int i = 0; i < cnt2; ++i){
dij.AddEdge(p0[i].x,p0[i].y,1);
dij.AddEdge(p0[i].y,p0[i].x,1);
dij.dijkstra(s);
if (dij.d[t] > L)continue;
pos = i;
break;
}
//printf("pos = %d\n",pos);
if (pos == -1)return 0 * puts("NO");
puts("YES");
for (int i = 0; i < cnt; ++i){
printf("%d %d %d\n",p[i].x,p[i].y,p[i].w);
}
for (int i = 0; i < pos; ++i)printf("%d %d %d\n",p0[i].x,p0[i].y,1);
printf("%d %d %d\n",p0[pos].x,p0[pos].y,L-dij.d[t] + 1);
for (int i = pos+1; i < cnt2; ++i)printf("%d %d %d\n",p0[i].x,p0[i].y,INF);
return 0;
}
/**
4 4 13 1 3
1 3 13
2 3 0
2 0 0
1 0 12

4 4 8 1 3
1 3 13
2 3 0
2 0 0
1 0 6
**/

ZS the Coder has drawn an undirected graph of n vertices numbered from 0 to n - 1 and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.

The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices s and t in the resulting graph is exactly L. Can you help him?

Input

The first line contains five integers n, m, L, s, t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 109, 0 ≤ s, t ≤ n - 1, s ≠ t) — the number of vertices, number of edges, the desired length of shortest path, starting vertex and ending vertex respectively.

Then, m lines describing the edges of the graph follow. i-th of them contains three integers, ui, vi, wi(0 ≤ ui, vi ≤ n - 1, ui ≠ vi, 0 ≤ wi ≤ 109). ui and vi denote the endpoints of the edge and wi denotes its weight. If wi is equal to 0 then the weight of the corresponding edge was erased.

It is guaranteed that there is at most one edge between any pair of vertices.

Output

Print "NO" (without quotes) in the only line if it's not possible to assign the weights in a required way.

Otherwise, print "YES" in the first line. Next m lines should contain the edges of the resulting graph, with weights assigned to edges which weights were erased. i-th of them should contain three integers ui, vi and wi, denoting an edge between vertices ui and vi of weight wi. The edges of the new graph must coincide with the ones in the graph from the input. The weights that were not erased must remain unchanged whereas the new weights can be any positive integer not exceeding 1018.

The order of the edges in the output doesn't matter. The length of the shortest path between s and t must be equal to L.

If there are multiple solutions, print any of them.

Examplesinput

output

input

2 1 123456789 0 1
0 1 0

output

YES
0 1 123456789

input

2 1 999999999 1 0
0 1 1000000000

output

NO

Note

Here's how the graph in the first sample case looks like :

$Codeforces Round #372 (Div. 2) -- D. Complete The Graph（Dijkstra单源最短路）$

In the first sample case, there is only one missing edge weight. Placing the weight of 8 gives a shortest path from 0 to 4 of length 13.

In the second sample case, there is only a single edge. Clearly, the only way is to replace the missing weight with 123456789.

In the last sample case, there is no weights to assign but the length of the shortest path doesn't match the required value, so the answer is "NO".

秒客网

Codeforces Round #372 (Div. 2) -- D. Complete The Graph（Dijkstra单源最短路）

相关文章