题意

　　求一个无向图中没有重边的两条最短路，并输出方案

分析

　　注意，是两条最短路！不是一条最短一条次短！所以先来个dijkstra/spfa来算一下最短路

　　根据dijkstra/spfa求出的dist[i]数组，建立一个新图，上面只有所有满足最短路的边构成的图

　　这样，建图就Ok了，下面如何解决没有重边呢？

　　很显然，设立一个源点和汇点，在源点出放出2的值。然后把刚刚建好的新图，边的权值设为1，相当于只能允许一个人经过。这样，如果在汇点得到了2的值，说明这样的两条路是存在的，再利用一个dfs求出即可。

　　注意dinic需要加上当前弧优化，不然会tle at #17

Accepted Code

1 {
      2         PROBLEM：sgu185  3         AUTHER:Rinyo  4         MEMO:最短路 网络流    5 }  6 Program sgu185;  7 Const  8   Infile = 'sgu185.in';  9   Outfile = ''; 10 Type 11   Rec = Record 12     y,s,flow:Longint; 13   End; 14 Var 15   map:Array[0..160000]Of REc; 16   a:Array[0..430,0..430]Of Longint; 17   dist,q,num,next,p:Array[0..430]Of Longint; 18   v:Array[0..430]Of Boolean; 19   maxflow,i,j,n,m,l:Longint; 20   flag:Boolean; 21 Function min(a,b:Longint):Longint; 22 Begin 23   if a0) And (dist[j]>mink+a[k,j]) Then dist[j]:=mink+a[k,j]; 52   End; 53 End; 54  55 Function dfs(now,value:Longint):Longint; 56 Var 57   v1,i,x,ff:Longint; 58 begin 59   if now=n Then Begin 60     dfs:=value; 61     Exit; 62   End; 63   v1:=value; 64   ff:=p[now]; 65   While ff>-1 Do Begin 66     i:=map[ff].y; 67     If (map[ff].flow>0) And (num[i]=num[now]+1) Then begin 68       x:=dfs(i,min(value,map[ff].flow)); 69       map[ff].flow:=map[ff].flow-x; 70       value:=value-x; 71       If odd(ff) Then map[ff+1].flow:=map[ff+1].flow+x 72                  Else map[ff-1].flow:=map[ff-1].flow+x; 73     End; 74     ff:=map[ff].s; 75     If value=0 then break; 76   End; 77   p[now]:=ff; 78   dfs:=v1-value; 79 End; 80  81 Procedure bfs; 82 Var 83   head,tail,now,ff,v:Longint; 84 Begin 85   Fillchar(q,sizeof(q),0); 86   Fillchar(num,sizeof(num),0); 87   head:=0;tail:=1;q[1]:=1;num[1]:=1;flag:=false; 88   While head
      
       -1 Do Begin 93       v:=map[ff].y; 94       If (map[ff].flow>0) And (num[v]=0) Then Begin 95         num[v]:=num[now]+1; 96         Inc(tail); 97         q[tail]:=v; 98         If v=n Then Begin 99           flag:=true;100           Exit;101         End;102       End;103       ff:=map[ff].s;104     End;105   End;106 End;107 108 Procedure answer(x:Longint);109 Var110   ff,v:Longint;111 Begin112   If (x=n) Then Begin113     WriteLn(n);114     Exit;115   End;116   ff:=next[x];117   While ff<>-1 Do Begin118     v:=map[ff].y;119     If (map[ff].flow=0) And (a[x,v]+dist[x]=dist[v]) Then begin120       Write(x,' ');121       answer(v);122       map[ff].flow:=1;123       Exit;124     End;125     ff:=map[ff].s;126   End;127 End;128 129 Begin130   Assign(input,infile);Reset(input);131   Assign(output,outfile);Rewrite(output);132   init;133   dijkstra;134   l:=0;135   Fillchar(next,sizeof(next),$ff);136   For i:=1 To n Do137     For j:=1 To n Do138       If (i<>j) And (a[i,j]>0) Then139         If dist[i]+a[i,j]=dist[j] Then Begin140           Inc(l);map[l].y:=j;map[l].flow:=1;map[l].s:=next[i];next[i]:=l;141           Inc(l);map[l].y:=i;map[l].flow:=0;map[l].s:=next[j];next[j]:=l;142         End;143   flag:=true;144   While flag Do Begin145     BFS;146     p:=next;147     maxflow:=maxflow+dfs(1,2);148   End;149   //WriteLn(maxflow);150   If maxflow<2 Then Begin151     WriteLn('No solution');152   End Else Begin153     answer(1);154     answer(1);155   End;156   Close(input);Close(output);157 End.158