NC207656. IrrationalGraph
描述
Mia is learning data structures, this semester. Knowing this, her boyfriend, John, gives her a difficult problem, which is about Graph.
There is adirected graph with n vertices, labeled 1, 2, ...,n, and m weighted edges (u1, v1, w1), (u2, v2, w2), ..., (um, vm, wm), the i-th of which means vertex ui can go to vertex vi and the cost will be wi (1 ≤ i ≤ m). Notice that the weights of the edges can be positive, zero, or negative. In the graph, k edges (u1, u2, w1), (u2, u3, w2), ..., (uk, uk+ 1, wk) is said to be a path from vertex u1 to vertex uk+ 1, and the total cost of the path would be w1 + w2 + ... + wk (k ≥ 0, and if k = 0, the cost would be 0). The shortest paths from vertex s to vertex t are defined to be the paths with minimum cost among all the paths from vertex s to vertex t. You are given a vertex s, and you can then find the shortest paths from vertex s to any vertices (including vertex s itself). Your task is to find out how many shortest paths there are from vertex s to all the vertices in this graph, respectively. The number may be quite large, so output the number modulo 20191208. In addition, it is quite clear that in some cases, the shortest paths from vertex s to some vertex do not exist, or there are infinite number of them, in which cases, the answer would be -1.
As this problem is a little bit hard for Mia, she, now, has turned to you for help!
输入描述
The first line is an integer T (1 ≤ T ≤ 20), indicates that there are T-group data.For each test case, the first line contains three integers n, m, s(1 ≤ s ≤ n ≤ 1,000, 1 ≤ m ≤ 100,000). n is the number of vertices in the graph. m is the number of edges in the graph. s is the given vertex.There are m lines following, the i-th of which contains three integers ui, vi, wi, indicating vertex ui can go to vertex vi and the cost will be wi (1 ≤ui, vi ≤n, -1,000 ≤ wi ≤ 1,000, 1 ≤ i ≤ m).
There are no more than 5 test cases with n > 100,m > 100.
输出描述
For each test case, output one line, which containsnintegers (separated by a space), thei-th of which is the number of shortest paths from vertex s to vertex i modulo 20191208 (1 ≤i≤n). If the shortest paths from vertex s to vertex i (1 ≤ i ≤ n) do not exist, or if there are infinite number of them, output -1 instead. The end of line does not have any extra spaces.
示例1
输入:
2 4 4 1 1 2 1 1 3 1 2 2 0 3 3 -1 5 6 1 1 2 1 2 3 2 3 5 1 2 4 1 4 5 2 2 5 3
输出:
1 -1 -1 -1 1 1 1 1 3
说明:
For the first test case, the shortest path from vertex 1 to vertex 1 is to stay still at vertex 1 and take no moves. We count this kind of staying still as 1 as well.
The shortest paths from vertex 1 to vertex 2 are: 1 -> 2, 1 -> 2 -> 2, 1 -> 2 -> ... -> 2, so there are infinite number of them.
The shortest paths from vertex 1 to vertex 3 do not exist, since you can go through the edge (3, 3, -1) repeatedly.
The shortest paths from vertex 1 to vertex 4 do not exist, because vertex 4 is beyond reach.
For the second test case, the shortest path from vertex 1 to vertex 1 is also to stay still.
The shortest path from vertex 1 to vertex 2 is: 1 -> 2.
The shortest path from vertex 1 to vertex 3 is: 1 -> 2 -> 3.
The shortest path from vertex 1 to vertex 4 is: 1 -> 2 -> 4.
The shortest paths from vertex 1 to vertex 5 are: 1 -> 2 -> 3 -> 5, 1 -> 2 -> 4 -> 5, and 1 -> 2 -> 5.
C++11(clang++ 3.9) 解法, 执行用时: 115ms, 内存消耗: 3688K, 提交时间: 2020-06-08 23:08:49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 20191208;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
struct graph
{
int head[maxn],nxt[maxn<<1],to[maxn<<1],w[maxn<<1],sz;
void init(){memset(head,-1,sizeof(head));sz=0;}
graph(){init();}
void push(int a,int b,int c){nxt[sz]=head[a],to[sz]=b,w[sz]=c,head[a]=sz++;}
int& operator[](const int a){return to[a];}
}g;
bool vis[maxn];
int dist[maxn],cnt[maxn],n;
bool no[maxn];
void spfa(int s)
{
queue<int>q;
q.push(s);
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[s]=0;
cnt[s]++;
while(!q.empty()){
int now = q.front();
q.pop();
vis[now]=0;
for(int i = g.head[now];~i;i = g.nxt[i]){
if(dist[g[i]]>=dist[now]+g.w[i]&&!no[g[i]]){
dist[g[i]]=dist[now]+g.w[i];
if(!vis[g[i]]){
cnt[g[i]]++;
if(cnt[g[i]]>n){
no[g[i]]=1;
continue;
}
vis[g[i]]=1;
q.push(g[i]);
}
}
}
}
}
int res[maxn],ans[maxn];
void bfs()
{
queue<int>q;
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;++i){
if(no[i]){
q.push(i);
vis[i]=1;
}
}
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = g.head[now];~i;i = g.nxt[i]){
if(vis[g[i]])continue;
no[g[i]]=1;
q.push(g[i]);
vis[g[i]]=1;
}
}
}
void spfa2(int s)
{
bfs();
if(no[s])return;
memset(vis,0,sizeof(vis));
res[s]=1;
queue<int>q;
q.push(s);
while(!q.empty()){
int now = q.front();
q.pop();
vis[now]=0;
for(int i = g.head[now];~i;i = g.nxt[i]){
if(dist[g[i]]==dist[now]+g.w[i]&&!no[g[i]]){
if(!vis[g[i]]){
vis[g[i]]=1;
res[g[i]]=res[now];
q.push(g[i]);
}
else {
res[g[i]]=(res[g[i]]+res[now])%mod;
}
}
}
ans[now]=(ans[now]+res[now])%mod;
res[now]=0;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("simple.in", "r", stdin);
freopen("simple.out", "w", stdout);
#endif
int t;
scanf("%d",&t);
while(t--){
memset(ans,0,sizeof(ans));
memset(no,0,sizeof(no));
memset(res,0,sizeof(res));
memset(cnt,0,sizeof(cnt));
g.init();
int m,s;
scanf("%d%d%d",&n,&m,&s);
for(int i = 1,a,b,c;i <= m;++i){
scanf("%d%d%d",&a,&b,&c);
g.push(a,b,c);
}
spfa(s);
spfa2(s);
for(int i = 1;i <= n;++i)printf("%d ",ans[i]==0?-1:ans[i]);
printf("\n");
}
return 0;
}