Path
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Given a graph with $n$ vertices and $m$ edges.Each vertex is numbered from $1$ to $n$.
Each edge $i$ has its cost $w_i$,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 $w_i-K(0 \le w_i-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 $w_i$,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 $w_i-K(0 \le w_i-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")
Input
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\le \sum_{}{}{m} ,\sum_{}{}{n} \le 10^6,1\le x,y,S \le n,1\le w,K\le 10^9$
$K \le w_i (1\le i \le 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\le \sum_{}{}{m} ,\sum_{}{}{n} \le 10^6,1\le x,y,S \le n,1\le w,K\le 10^9$
$K \le w_i (1\le i \le m)$
Output
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".
Sample Input
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
Sample Output
0 4 5 8 10 0 4 5 8 8
Source
2022“杭电杯”中国大学生算法设计超级联赛（1）