题意：求1->n的两条不相交的最短路（两条路径可以共顶点但是不能共边)
心得：看了AC的博客学的，呵呵，这题充分展示了一切皆是网络流的核心思想。做法：首先找出以1为顶点的最短路径树，1到树中任意一点的连线都是最短路径，首先把这些边加到网络流的边集中，容量为1。
然后再枚举下边，将不在最短路径树上但是在最短路上的边也加到网络流的边集中，容量为1。跑一遍1到n的最大流，如果流量>=2则有解，再从原点深搜路径即可。
确切的来说，只要在后来建的图中随便找一条路径均是原点到该点的最短路（注意边是单向的），又因为限制了流量是1，所以一条边只能选取一次，这样跑出来的流量就一定是不相交最短路的条数。
int mat[maxn][maxn];
int n,m;
int dis[maxn];
int use[maxn];
void SPFA(int n,int s)
{
fill(dis,dis+n,INF);
fill(use,use+n,0);
queue<int>Q;
dis[s]=0;
use[s]=1;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();Q.pop();
use[x]=0;
for(int i=0;i<n;i++)
{
if(dis[x]+mat[x][i]<dis[i])
{
dis[i]=dis[x]+mat[x][i];
if(!use[i])
{
use[i]=1;
Q.push(i);
}
}
}
}
}
int flag=0;
void dfs(int x)
{
if(flag==1)return;
if(x==n-1)
{
flag=1;
printf("%d\n",x+1);
return;
}
else printf("%d ",x+1);
for(node *p=adj[x];p;p=p->next)
{
if((p-edge)&1)continue;
if(p->flow==0) {
p->flow=-1;
dfs(p->v);
if(flag==1)
return;
}
}
}
int main()
{
scanf("%d %d",&n,&m);
int a,b,c;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)mat[i][j]=0;
else mat[i][j]=INF;
}
}
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
a--;b--;
if(c<mat[a][b])
mat[a][b]=mat[b][a]=c;
}
SPFA(n,0);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j)continue;
if(dis[i]+mat[i][j]==dis[j])
insert(i,j,1);
}
int ans=sap(n,0,n-1);
if(ans<2){
printf("No solution\n");
return 0;
}
flag=0;
dfs(0);
flag=0;
dfs(0);
return 0;
}
很难得的一次写对了SPFA...
参考了AC大神的代码，递归删除边的时候将流量置为-1,不错的想法。另外我用p-edge的奇偶性判断正反边，但是一直没弄明白p和edge都是地址而且地址相差并不是1的时候减出来却是1。。。