[HAOI2005]路由问题，第二短路

【问题描写叙述】

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至少有两条不同路径)

【输入输出例子】

[HAOI2005]路由问题，第二短路

file=/2397/mod_programming/intro/t1-01.jpg" height="258" width="438" alt="" style="border:0px">

lyxzwt.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

lyxzwt.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

求出记录最短路的一条路径。然后删边求次短路。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 100;

const int INF = 1e9;

int g[maxn][maxn];

int d[maxn], pre[maxn], p[maxn], P, n, s, t;

int path[maxn][2], e;

bool vis[maxn];

void init()

{

    scanf("%d%d%d", &n, &s, &t);

    for(int i=1; i<=n; ++i) {

        for(int j=1; j<=n; ++j) {

            scanf("%d", &g[i][j]);

            if(g[i][j]==0) {

                g[i][j] = INF;

            }

        }

    }

    scanf("%d", &P);

    for(int i=1; i<=n; ++i) scanf("%d", &p[i]);

}

int dijkstra()

{

    for(int i=1; i<=n; ++i) d[i] = INF;

    memset(pre, -1, sizeof pre );

    memset(vis, 0, sizeof vis );

    d[s] = 0;

    for(int i=1; i<=n; ++i) {

        int k = -1;

        for(int j=1; j<=n; ++j) if(!vis[j] &&(k==-1||d[j]<d[k]) ) {

                k = j;

            }

        if(-1==k) break;

        vis[k] = 1;

        for(int j=1; j<=n; ++j) if(!vis[j]&&d[j]>d[k]+g[k][j]) {

                d[j] = d[k] + g[k][j];

                pre[j] = k;

            }

    }

    return d[t];

}

void solve()

{

    int s0, s1, s2;

    s1 = dijkstra();

    int u = t;

    e = 0;

    while(~pre[u]){

        path[e][0] = u;

        path[e][1] = pre[u];

        e++;

        u = pre[u];

    }

    s2 = INF;

    for(int i=0; i<e; ++i){

        int &u = path[i][0], &v = path[i][1];

        int tmp = g[u][v];

        g[u][v] = g[v][u] = INF;

        int res = dijkstra();

        g[u][v] = g[v][u] = tmp;

        s2 = min(s2, res);

    }

    for(int i=1; i<=P; ++i){

        int &u = p[i];

        for(int v=1; v<=n; ++v)

            g[u][v] = g[v][u] = INF;

    }

    s0 = dijkstra();

    printf("%d %d %d\n", s0, s1, s2);

}

int main()

{

    freopen("lyxzwt.in", "r", stdin);

    freopen("lyxzwt.out", "w", stdout);

    init();

    solve();

    return 0;

}

秒客网

[HAOI2005]路由问题，第二短路

相关文章