前兩問是最短路，第三問是標準的次短路徑。求法是先求出最短路徑，然後枚舉每條從S到T的最短路徑上的邊，刪除以後再求一次最短路徑，保留最小值就是次短路徑。

/* 
 * Problem: HAOI2005 route
 * Author: Guo Jiabao
 * Time: 2009.4.14 14:05
 * State: Solved
 * Memo: Dijkstra 次短路徑
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=51,MAXM=MAXN*MAXN*2,INF=0x7FFFFFF;
using namespace std;
struct edge
{
    edge *next,*op;
    int t,c;
}ES[MAXM],*V[MAXN],*SPE[MAXN];
int N,S,T,P,SPC,S0,S1,S2,EC=-1;
int sp[MAXN];
bool mf[MAXN],vis[MAXN];
inline void addedge(int a,int b,int c)
{
    ES[++EC].next=V[a];
    V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
    ES[++EC].next=V[b];
    V[b]=ES+EC; V[b]->t=a; V[b]->c=c;
    V[a]->op=V[b]; V[b]->op=V[a];
}

int adjm[MAXN][MAXN];
void init()
{
    int i,j,c;
    freopen("route.in","r",stdin);
    freopen("route.out","w",stdout);
    scanf("%d%d%d",&N,&S,&T);
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=N;j++)
        {
            scanf("%d",&c);
            adjm[i][j]=c;
            if (i>=j && adjm[i][j]!=adjm[j][i])
                c=1575;
            if (i<j && c)
                addedge(i,j,c);
        }
    }
    scanf("%d",&P);
    for (i=1;i<=P;i++)
    {
        scanf("%d",&c);
        mf[c]=true;
    }
}
void dijkstra()
{
    int i,j,Mini;
    for (i=1;i<=N;i++)
        sp[i]=INF,vis[i]=false;
    sp[S]=0;
    for (i=S;i;)
    {
        vis[i]=true;
        for (edge *e=V[i];e;e=e->next)
        {
            if (!mf[j=e->t] && sp[i] + e->c < sp[j])
                sp[j]=sp[i] + e->c;
        }
        Mini=INF;i=0;
        for (j=1;j<=N;j++)
            if (!vis[j] && sp[j] < Mini)
            {
                Mini=sp[j];
                i=j;
            }
    }
}
void dfs(int i)
{
    vis[i]=true;
    for (edge *e=V[i];e;e=e->next)
    {
        int j=e->t;
        if (sp[j] + e->c == sp[i])
        {
            SPE[++SPC]=e->op;
            if (!vis[j])
                dfs(j);
        }
    }
}
void solve()
{
    int i,c;
    S2=INF;
    dijkstra();
    S0=sp[T];
    memset(mf,0,sizeof(mf));
    dijkstra();
    S1=sp[T];
    memset(vis,0,sizeof(vis));
    dfs(T);
    for (i=1;i<=SPC;i++)
    {
        edge *e=SPE[i];
        c=e->c;
        e->c=INF;
        dijkstra();
        e->c=c;
        c=sp[T];
        if (c<S2)
            S2=c;
    }
}
int main()
{
    init();
    solve();
    printf("%d %d %dn",S0,S1,S2);
    return 0;
}

<div class="MainText">
<p class="MsoNormal"><a href="http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=22" target="_blank">http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=22</a></p>
<p class="MsoNormal"><span>【問題描述】</span></p>

<p class="MsoNormal">X城有一個含有N個節點的通信網絡，在通信中，我們往往關心信息從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。
任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。
任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。
<p class="MsoNormal">【輸入文件】</p>

<p class="MsoNormal">第1行： N I J (節點個數 起始節點 目標節點)
第2—N+1行： Sk1 Sk2…SkN  (節點K到節點J的距離爲SkJ K=1，2，……，N)
最後一行： P T1 T2……Tp (故障節點的個數及編號)
<p class="MsoNormal">【輸出文件】</p>

S0 S1 S2 (S1&lt;=S2 從節點I到節點J至少有兩條不同路徑)
<p class="MsoNormal">【輸入輸出樣例】</p>

<p class="MsoNormal" align="center"><span lang="EN-US"><a href="http://www.ruvtex.cn/images/t1-01.jpg"><img src="http://www.ruvtex.cn/images/t1-01.jpg" alt="" width="315" height="186" /></a>
</span>
<p class="MsoNormal">route.in</p>

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
<p class="MsoNormal"><span lang="EN-US">【約束條件】</span></p>

<p align="left">(1)N&lt;=50 N個節點的編號爲1，2，…，N
(2)Skj爲整數，Skj&lt;=100，(K，J=1，2…，N  若Skj=0表示節點K到節點J沒線路)
(3)P&lt;=5<span lang="EN-US"> </span>

</div>