OI 国有 N 座城市，每座城市有唯一的 1 到 N 的标号。其中 1 号城市为首都。 OI 国的交通 十分发达，共有 M 条有向道路，已知通过第 i 条道路所需时间为 ti。 林大帝的统治使 OI 国走向了繁荣。 不幸的是，各地都仍旧有一些不老实的人在捣蛋。林大帝实在是不能忍了。为了加强治安， 保障国土的完整，林大帝派人在每座城市（除了首都本身）招募军队去剿匪。匪徒都是些乌合 之众，没过一会儿就被林大帝的精锐之师打得落花流水、心服口服。 为了庆祝剿匪胜利，各地的军队都必须尽快到首都集合。然而，行军是会产生劳累值的，且 军队在剿匪之后十分疲惫，所以他们会优先选择劳累值最小的路径。如果有多个劳累值最小的 路径，他们会在其中选择用时最少的路径。 当军队经过一条 u 到 v 的道路时，如果 v 能够到达 u，士兵们就会有绕圈的感觉，故产生 1 单位的劳累值；否则，士兵们会有说有笑地前进，不会产生劳累值。一条路径的劳累值为路径 上所有边的劳累值之和，一条路径的用时为路径上所有边的用时之和，如有边重复经过需累计。 你需要对每座城市计算其军队将选择的路径的劳累值及用时，或指出无法到达首都。
输出共 N − 1 行，第 i 行描述 i + 1 号城市的军队选择的路径情况。如果该城市的军队不能 到达首都，输出 -1；否则输出两个整数依次表示劳累值和用时。
通过计算用时可以感知出是一个最短路问题，但是多了劳累值的问题，稍微复杂一点
但是要使u能到v并且v能到u,对于有向图来说，很明显是在一个环里，所以我们只需要将强连通分量染色，再给边标上第二层边权，如果两节点为同一个强连通分量里，则边权标为1，否则标为0。
之后通过最短路算法，同时计算时间和劳累值的最小，但是按照劳累值优先。
注意建图需要反向建！
#include<bits/stdc++.h> using namespace std; #define N 100100 #define INF 0X7fffffff7fffffff #define ll long long ll low[N],dfn[N],first[N],head[N],vis[N],col[N],v[N],u[N],w[N],t[N],d[N]; ll n,m,dep,cnt,gro,cot; struct email { ll u,v,w; ll nxt; }e[N*4],g[N*4]; queue<ll>q; stack<ll>s; inline void add(ll u,ll v,ll w) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v;e[cnt].w=w; } inline void readd(ll u,ll v,ll w) { g[++cot].nxt=head[u];head[u]=cot; g[cot].u=u;g[cot].v=v;g[cot].w=w; } void spfa(ll x) { q.push(x);vis[x]=1;t[x]=0;d[x]=0; while(!q.empty()) { ll u=q.front();q.pop();vis[u]=0; for(ll i=head[u];i;i=g[i].nxt) { ll v=g[i].v,tim=g[i].w,w=e[i].w; if(t[v]>t[u]+tim) { t[v]=t[u]+tim; d[v]=d[u]+w; if(!vis[v]) { q.push(v); vis[v]=1; } } if(t[v]==t[u]+tim) if(d[v]>d[u]+w) { d[v]=d[u]+w; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } void tarjan(ll u) { low[u]=dfn[u]=++dep; s.push(u);vis[u]=1; for(ll i=first[u];i;i=e[i].nxt) { ll v=e[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { gro++; while(1) { ll tt=s.top();s.pop(); col[tt]=gro; vis[tt]=0; if(tt==u)break; } } } int main() { scanf("%lld%lld",&n,&m); for(ll i=1;i<=m;i++) { scanf("%lld%lld%lld",&u[i],&v[i],&w[i]); add(v[i],u[i],w[i]); } tarjan(1); for(ll i=1;i<=m;i++) { ll u1=u[i],v1=v[i],w1; if(col[u1]==col[v1]) w1=1; else w1=0; readd(v1,u1,w1); } memset(vis,0,sizeof(vis)); for(ll i=1;i<=n;i++) t[i]=INF,d[i]=INF; spfa(1); for(ll i=2;i<=n;i++) { if(t[i]==INF||d[i]==INF) printf("-1\n"); else printf("%lld %lld\n",t[i],d[i]); } }
原文：https://www.cnblogs.com/NSD-email0820/p/9483477.html