6545: Path
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：9
解决：3
题目描述
Given a graph with n vertices and m edges. Each vertex is numbered from 1 to n.
Each edge i has its cost wi, some edges are common edges and some edges are special edges.
When you pass through a special edge, the next step after passing this edge, you can reach any vertex in the graph. If you goto the vertex which an original edge i can arrive from current vertex, the cost becomes wi−K (0≤ wi−K )(if you used edge i ), otherwise the cost will become 0(every vertex except the vertex which original edge can arrive from current vertice)
original edge includes all common edges and special edges.
Now you start at S,You need to calculate the minimum cost from the starting vertex to each vertex(If there is a situation where you cannot reach, please output "-1")
Each edge i has its cost wi, some edges are common edges and some edges are special edges.
When you pass through a special edge, the next step after passing this edge, you can reach any vertex in the graph. If you goto the vertex which an original edge i can arrive from current vertex, the cost becomes wi−K (0≤ wi−K )(if you used edge i ), otherwise the cost will become 0(every vertex except the vertex which original edge can arrive from current vertice)
original edge includes all common edges and special edges.
Now you start at S,You need to calculate the minimum cost from the starting vertex to each vertex(If there is a situation where you cannot reach, please output "-1")
输入
Each test contains multiple test cases. The first line contains the number of test cases T. Description of the test cases follows.
The first line of each test case contains four integers n,m,S,K
The next m lines each line contains four integers x,y,w,t represent an directed edge connect x and y with cost w,t =0 represents it's a common edge, t =1 represents it's a special edge.
1≤∑m,∑n≤106,1≤x,y,S≤n,1≤w,K≤109
K≤wi(1≤i≤m)
The first line of each test case contains four integers n,m,S,K
The next m lines each line contains four integers x,y,w,t represent an directed edge connect x and y with cost w,t =0 represents it's a common edge, t =1 represents it's a special edge.
1≤∑m,∑n≤106,1≤x,y,S≤n,1≤w,K≤109
K≤wi(1≤i≤m)
输出
For each test case, print n integer in a line— the answer to the problem.
There is a space at the end of the line for each line,when you cannot reach, please output "-1".
There is a space at the end of the line for each line,when you cannot reach, please output "-1".
样例输入 复制
2
5 4 1 1
1 2 4 0
1 3 5 0
3 4 3 1
4 5 3 0
5 3 1 1
1 2 4 0
1 3 5 0
3 4 3 1样例输出 复制
0 4 5 8 10
0 4 5 8 8