思路
这题要求的是带负权边的最短路，显然不能直接用Dijkstra。然而Bellman-Ford或SPFA的时间复杂度最坏$O(NM)$，而且众所周知，USACO总是卡SPFA的。尽管这题数据比较老，因此SPFA+SLF可以水过，但是正解并不是如此。
顺便说一下，用优先队列优化SPFA并不有效(来自[模板]单源最短路-题解)，在这题比普通SPFA更慢。然而在某些边权为正的卡SPFA的图中，几乎和Dijkstra不相上下。
可以发现，图有一个很强的性质：对于无向边，边权总是正的，因此每个无向边联通块是强联通的。而可能的负权边保证不能反向联通，因此把无向边联通块缩点后，得到的就是DAG。这样就可以在块内使用Dijkstra，块间利用拓扑排序更新答案。时间复杂度$O(M\log N)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
const int N=25005,INF=0x3f3f3f3f;
typedef pair<int,int> pii;
vector<pii> roads[N],planes[N];
vector<int> comp[N];
//联通分量中的点
int belong[N],indeg[N],d[N];
//belong[]表示每个点所属的联通分量，indeg[]表示联通分量的入度
bool vis[N];
void dfs(int k,int num)
{
belong[k]=num;
comp[num].push_back(k);
for(auto e:roads[k])
if(!belong[e.first])
dfs(e.first,num);
}
//dfs洪水填充
int main()
{
int n,m,p,s;
cin>>n>>m>>p>>s;
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
roads[u].push_back(make_pair(v,w));
roads[v].push_back(make_pair(u,w));
}
while(p--)
{
int u,v,w;
cin>>u>>v>>w;
planes[u].push_back(make_pair(v,w));
}
int c=0;
for(int i=1;i<=n;i++)
if(!belong[i])
dfs(i,++c);
for(int i=1;i<=n;i++)
for(auto e:planes[i])
indeg[belong[e.first]]++;
fill(d+1,d+n+1,INF);
d[s]=0;
queue<int> Q;
for(int i=1;i<=c;i++)
if(!indeg[i])
Q.push(i);
while(!Q.empty())
{
int k=Q.front();Q.pop();
priority_queue<pii,vector<pii>,greater<pii>> PQ;
for(auto i:comp[k])
if(d[i]<INF)
PQ.push(make_pair(d[i],i));
while(!PQ.empty())
{
pii k=PQ.top();PQ.pop();
if(vis[k.second])
continue;
vis[k.second]=true;
for(auto e:roads[k.second])
if(d[k.second]+e.second<d[e.first])
PQ.push(make_pair(d[e.first]=d[k.second]+e.second,e.first));
for(auto e:planes[k.second])
d[e.first]=min(d[e.first],d[k.second]+e.second);
}
for(auto i:comp[k])
for(auto e:planes[i])
if(--indeg[belong[e.first]]==0)
Q.push(belong[e.first]);
}
//拓扑排序和Dijkstra
for(int i=1;i<=n;i++)
if(d[i]==INF)
cout<<"NO PATH\n";
else
cout<<d[i]<<endl;
return 0;
}
拓展：生成数据
这题很有趣，因此我思考了如何生成数据。直接随机显然不符合题意，需要一定的构造。我的方法是：可以先确定每个点所属的连通分量，然后在连通分量中生成树保证连通，再在连通分量内随机添加边。然后在连通分量间生成树保证连通，再随机加边。只要规模足够大，用这种方法生成的数据足以卡掉SPFA了。
附代码供参考(C++11)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
ofstream fout("roadplane.in");
const int n=100000,m=300000,w=50000,cn=1000,W=100000;
int belong[n+5];
vector<int> comp[cn+5];
int f[n+5];
int getf(int x)
{
return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
minstd_rand gen(time(NULL));
for(int i=1;i<=n;i++)
{
uniform_int_distribution<> dc(1,cn);
belong[i]=dc(gen);
comp[belong[i]].push_back(i);
}
assert(comp[1].size());
uniform_int_distribution<> d(0,comp[1].size()-1);
fout<<n<<' '<<m<<' '<<w<<' '<<comp[1][d(gen)]<<endl;
for(int i=1;i<=cn;i++)
{
int cnt=0;
for(int j=0;j<comp[i].size();j++)
f[j]=j;
while(cnt+1<comp[i].size())
{
uniform_int_distribution<> did(0,comp[i].size()-1);
int u=did(gen),v=did(gen),ru=getf(u),rv=getf(v);
if(ru!=rv)
{
f[ru]=rv;
cnt++;
uniform_int_distribution<> dw(0,W);
fout<<comp[i][u]<<' '<<comp[i][v]<<' '<<dw(gen)<<endl;
}
}
}
for(int i=n-cn+1;i<=m;i++)
{
uniform_int_distribution<> dc(1,cn);
int c=dc(gen);
if(!comp[c].size())
{
i--;
continue;
}
uniform_int_distribution<> did(0,comp[c].size()-1),dw(0,W);
fout<<comp[c][did(gen)]<<' '<<comp[c][did(gen)]<<' '<<dw(gen)<<endl;
}
for(int i=1;i<=cn;i++)
f[i]=i;
for(int i=1;i<cn;)
{
uniform_int_distribution<> dc(1,cn-1);
int cu=dc(gen);
uniform_int_distribution<> dc1(cu+1,cn);
int cv=dc1(gen),rcu=getf(cu),rcv=getf(cv);
if(rcu==rcv)
continue;
f[rcu]=rcv;
if(!comp[cu].size()||!comp[cv].size())
continue;
uniform_int_distribution<> didu(0,comp[cu].size()-1),didv(0,comp[cv].size()-1),dw(-W,W);
fout<<comp[cu][didu(gen)]<<' '<<comp[cv][didv(gen)]<<' '<<dw(gen)<<endl;
i++;
}
for(int i=cn;i<=w;)
{
uniform_int_distribution<> dc(1,cn-1);
int cu=dc(gen);
uniform_int_distribution<> dc1(cu+1,cn);
int cv=dc1(gen);
if(!comp[cu].size()||!comp[cv].size())
continue;
uniform_int_distribution<> didu(0,comp[cu].size()-1),didv(0,comp[cv].size()-1),dw(-W,W);
fout<<comp[cu][didu(gen)]<<' '<<comp[cv][didv(gen)]<<' '<<dw(gen)<<endl;
i++;
}
return 0;
}