[次短路徑]HAOI2005 路由選擇問題 route 解題報告

路由選擇問題

【問題描述】

    X城有一個含有N個節點的通信網絡，在通信中，我們往往關心資訊從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。

任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。

任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。

【輸入文件】

第1行： N I J (節點個數 起始節點 目標節點)

第2—N+1行： Sk1 Sk2…SkN (節點K到節點J的距離爲SkJ K=1，2，……，N)

最後一行： P T1 T2……Tp (故障節點的個數及編號)

【輸出文件】

S0 S1 S2 (S1<=S2 從節點I到節點J至少有兩條不同路徑)

【輸入輸出樣例】

route.in

5 1 5

0 10 5 0 0

10 0 0 6 20

5 0 0 30 35

0 6 30 0 6

0 20 35 6 0

1 2

route.out

40 22 30

【約束條件】

(1)N<=50 N個節點的編號爲1，2，…，N

(2)Skj爲整數，Skj<=100，(K，J=1，2…，N 若Skj=0表示節點K到節點J沒線路)

(3)P<=5 　

【分析】

這題很沒意思啊～想要求次短路就直接問唄，還弄幾個壞節點～

數據規模很小，N<=50，這麼小的數據規模很不符合『省選』的風格啊，這哪怕時亂搞一個O(N^4)的算法也能過～雖然我的是次短路時O(N^2*M)的～

這道題目需要存爲有向圖。

第一問求最短路（需要排除幾個故障節點），把壞掉的節點標記一下，

在單源最短路算法中擴展時跳過就行了～我寫了Dijkstra。

第二問也是求最短路，只不過不考慮故障的頂點，只需要把剛纔標記的節點再去掉標記然後再Dijkstra一下就行了。

第三問是次短路徑，雖然可以用求K短路徑的Yen算法，但是這畢竟時『次』短啊，只需要枚舉最短路徑的每條邊，將它刪去然後求最短路，找出他們的最小的最短路即爲次短路。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25474

001 /*
002 * Problem: HAOI2005 路由選擇問題
003 * Author: Yee-fan Zhu
004 * Website: http://zhuyf.tk/
005 * Method: (2nd) Shortest-Path
006 * Algorithm: Dijkstra
007 * Cost: 0.000s
008 * Memory: 472KB
009 */
010 #include <cstdio>
011 #include <cstdlib>
012 #include <cstring>
013 using namespace std;
014 const int INF=100000000;
015 const int MAXN=51;
016 int  Wasu[MAXN];//壞掉的節點
017 int N;//總節點數
018 int P;//壞掉的節點數
019 int S,T;//起訖點
020
021 class Graph
022 {
023 public:
024     int Map[MAXN][MAXN];//臨接矩陣存圖
025     int dist[MAXN];
026     int prev[MAXN];
027     int flag[MAXN];
028     int Node[MAXN];
029     int Top;
030     int ShortestPath()
031     {
032         int ans;
033         for(int i=1;i<=N;i++)
034         {
035             dist[i]=INF;
036             flag[i]=0;
037             prev[i]=0;
038         }
039        
040         for(int i=1;i<=N;i++)
041         {
042             if(Map[S][i]==0 || Wasu[i]==0)
043                 continue;
044             dist[i]=Map[S][i];
045             prev[i]=S;
046         }
047        
048         dist[S]=0;
049         flag[S]=1;
050        
051         for(int i=2;i<=N;i++)
052         {
053             int tmp=INF;
054             int u=S;
055             for(int j=1;j<=N;j++)
056             {
057                 if((!flag[j]) && dist[j]<tmp && Wasu[j]==1)
058                 {
059                     u=j;
060                     tmp=dist[j];
061                 }
062             }
063             flag[u]=1;
064             for(int j=1;j<=N;j++)
065             {
066                 if(flag[j]==1)
067                     continue;
068                 if(Map[u][j]==0)
069                     continue;
070                 if(Wasu[j]==0)
071                     continue;
072                 int newdist=dist[u]+Map[u][j];
073                 if(newdist<dist[j])
074                 {
075                     dist[j]=newdist;
076                     prev[j]=u;
077                 }
078             }
079         }
080         ans=dist[T];
081         return ans;
082     }
083    
084     void GetPath()
085     {
086         Top=1;
087         int p=T;
088         for(int i=1;i<=N;i++)
089             Node[i]=0;
090         while(p!=S)
091         {
092             Node[Top]=p;
093             p=prev[Node[Top]];
094             Top++;
095         }
096         Node[Top]=S;    
097        
098         int tt[MAXN];
099         for(int i=1;i<=Top;i++)
100             tt[i]=Node[Top-i+1];
101         for(int i=1;i<=Top;i++)
102             Node[i]=tt[i];
103     }
104    
105     void NewGraph(Graph *New,int x)
106     {
107         for(int i=1;i<=N;i++)
108             for(int j=1;j<=N;j++)
109                 New->Map[i][j]=Map[i][j];
110         New->Map[Node[x]][Node[x+1]]=0;       
111     }
112 }G,Sec;
113
114 void init()
115 {
116     scanf("%d %d %d\n",&N,&S,&T);
117     for(int i=1;i<=N;i++)
118     {
119         Wasu[i]=1;
120         for(int j=1;j<=N;j++)
121             scanf("%d",&G.Map[i][j]);
122     }
123     scanf("%d",&P);
124     int tmp;
125     for(int i=1;i<=P;i++)
126     {
127         scanf("%d",&tmp);
128         Wasu[tmp]=0;
129     }
130     return;
131 }
132
133 void Solve()
134 {
135     int Ans1=G.ShortestPath();
136     for(int i=1;i<=N;i++) Wasu[i]=1;
137     int Ans2=G.ShortestPath();
138     printf("%d %d ",Ans1,Ans2);
139    
140     G.GetPath();
141    
142     int top=G.Top;
143     /*printf("%d\n",top);*/
144     int Min=INF;
145     int res;
146     for(int i=1;i<top;i++)
147     {
148         G.NewGraph(&Sec,i);
149         res=Sec.ShortestPath();
150         if(res<Min)
151             Min=res;
152     }
153     printf("%d\n",Min);
154 }
155
156 int main()
157 {
158     freopen("route.in","r",stdin);
159     freopen("route.out","w",stdout);
160     init();   
161     Solve();
162     return 0;   
163 }