第一二个问是标准的最短路经没什么好说，直接用Dijkstra或SPFA即可。只要是第三个问，求次短路。
简单的求次短路方法和求次小生成树基本一样，也是枚举删除一条最短路上的边，在求最短路，再从求出
的值中找出最小的即可。
次短路还有一些扩展可以查看byvoid大牛的blog。
1 /*
2 * Problem: HAOI 2005 路由选择问题
3 * Author: Xu Fei
4 * Time: 2010.8.2 13.59
5 * Method: Dijkstra 次短路
6 */
7
8 #include<iostream>
9 #include<cstdio>
10 #include<cstring>
11 using namespace std;
12
13 const int MaxN=55,INF=0xFFFFFFF;
14
15 struct Node{
16 int x,y;
17 }Path[MaxN];
18
19 int N,S,T,Lp,Len;
20 int S0,S1,S2;
21 int P[MaxN];
22 int dis[MaxN];
23 bool vis[MaxN];
24 int pre[MaxN];
25 int temp[MaxN][MaxN];
26 int cost[MaxN][MaxN];
27
28 void into()
29 {
30 int i,j;
31
32 scanf("%d%d%d",&N,&S,&T);
33 for(i=1;i<=N;++i)
34 {
35 for(j=1;j<=N;++j)
36 {
37 scanf("%d",&cost[i][j]);
38 if(cost[i][j]==0)
39 cost[i][j]=INF;
40 }
41 }
42 scanf("%d",&Lp);
43 for(i=1;i<=Lp;++i)
44 scanf("%d",P+i);
45 }
46 void change(bool flag)
47 {
48 int i,j;
49
50 if(flag)
51 {
52 memcpy(temp,cost,sizeof(cost));
53 for(i=1;i<=Lp;++i)
54 for(j=1;j<=N;++j)
55 cost[P[i]][j]=INF;
56 }
57 else
58 {
59 memcpy(cost,temp,sizeof(cost));
60 }
61 }
62 int dijkstra()
63 {
64 int i,j,Min,kj;
65
66 for(i=1;i<=N;++i)
67 {
68 dis[i]=cost[S][i];
69 vis[i]=true;
70 pre[i]=S;
71 }
72 dis[S]=0;
73 vis[S]=false;
74 for(i=1;i<N;++i)
75 {
76 Min=INF;
77 for(j=1;j<=N;++j)
78 if(vis[j]&&dis[j]<Min)
79 Min=dis[j],kj=j;
80 if(kj==T) break;
81 vis[kj]=false;
82 for(j=1;j<=N;++j)
83 if(vis[j]&&dis[j]>dis[kj]+cost[kj][j])
84 {
85 dis[j]=dis[kj]+cost[kj][j];
86 pre[j]=kj;
87 }
88 }
89 return dis[T];
90 }
91 void solve()
92 {
93 int i,tmp,Min;
94
95 change(true);
96 S0=dijkstra();
97 change(false);
98 S1=dijkstra();
99 Len=0;
100 i=T;
101 while(i!=S)
102 {
103 Len++;
104 Path[Len].x=pre[i];
105 Path[Len].y=i;
106 i=pre[i];
107 }
108 S2=INF;
109 for(i=1;i<=Len;++i)
110 {
111 tmp=cost[Path[i].x][Path[i].y];
112 cost[Path[i].x][Path[i].y]=INF;
113 cost[Path[i].y][Path[i].x]=INF;
114 Min=dijkstra();
115 cost[Path[i].x][Path[i].y]=tmp;
116 cost[Path[i].y][Path[i].x]=tmp;
117 if(S2>Min)
118 S2=Min;
119 }
120 printf("%d %d %d\n",S0,S1,S2);
121 }
122 int main()
123 {
124 freopen("t.in","r",stdin);
125 freopen("t.out","w",stdout);
126
127 into();
128 solve();
129 return 0;
130 }
路由选择问题(T1)
【问题描述】
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至少有两条不同路径)
t1.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
t2.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
posted on 2010-08-02 14:02
xfstart07 阅读(227)
评论(0) 编辑 收藏 引用 所属分类:
竞赛题库 、
图论