国际大学生程序设计竞赛例题_4.9道路重建

1,题意:原来道路连通图,现在几条路坏了,要求点m和n必须连通,求出最小的代价.
2,解决:转化Dijkstra算法,原来连通的权值设为0,求m和n的最短路径.
3,实现代码:

#include <iostream>
using namespace std;

const int maxN=101;
const int inf=100000000;
int graph[maxN][maxN]; //无向图
int dis[maxN];//距离矩阵 到顶点的距离
bool use[maxN];//标志点是否处理

int graph2[maxN][maxN]; //无向图


int cnt; //测试数目
int vNum;//顶点数
int eNum;//边数

void dijk(int s)
{
    for(int i=1;i<=vNum;i++)
    {
        dis[i]=inf;
        use[i]=false;
    }
    int u,temp;
    while(1)
    {
        temp=inf;
        dis[s]=0;
        for(int i=1;i<=vNum;i++)
        {
            if(!use[i]&&dis[i]<temp)
            {
                temp=dis[i];
                u=i;
            }
        }
        if(temp==inf) break;
        use[u]=true;
        for(int i=1;i<=vNum;i++)
        {
            if( !use[i] && graph2[u][i]!=-1 && dis[i]>dis[u]+graph2[u][i] )
                dis[i]=dis[u]+graph2[u][i];
        }
    }
}

int main()
{
    freopen("4.9.in","r",stdin);
    int x,y,d;
    int dnum;//破坏的道路数
    int s,t;
    while(cin>>vNum,vNum)
    {
        memset(graph,-1,sizeof(graph));
        cin>>eNum;
        while(eNum--)
        {
            cin>>x>>y>>d;
            graph[x][y]=graph[y][x]=d;
        }
        for(int i=1;i<=vNum;i++)
            for(int j=1;j<=vNum;j++)
            {
                if(graph[i][j]==-1) graph2[i][j]=-1;
                else graph2[i][j]=0;
            }
        cin>>dnum;
        while(dnum--)
        {
            cin>>x>>y;
            graph2[x][y]=graph2[y][x]=graph[x][y];
        }
        cin>>s>>t;
        dijk(s);
        cout<<dis[t]<<endl;
    }
    return 0;
}