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;
}
分享到:
相关推荐
《国际大学生程序设计竞赛例题解.三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的...
本系列丛书包括《ACM国际大学生程序设计竞赛:知识与入门》、《ACM国际大学生程序设计竞赛:算法与实现》、《ACM国际大学生程序设计竞赛:题目与解读》、《ACM国际大学生程序设计竞赛:比赛与思考》等4册,其中《ACM...
国际大学生程序设计竞赛例题解(六) 广东省大学生程序设计竞赛例题解析
### 国际大学生程序设计竞赛教程知识点概览 #### 一、国际大学生程序设计竞赛(ACM/ICPC)概述 - **主办单位**: ACM/ICPC由国际计算机学会(Association for Computer Machinery, ACM)主办,该学会是全球历史最...
第二本:国际大学生程序设计竞赛例题解 2 广东省大学生程序设计竞赛试题 2003-2005年 第三本:国际大学生程序设计竞赛例题解 3 图论·动态规划算法·综合题专集 第四本:国际大学生程序设计竞赛例题解 4 广东省...
此资源压缩包分为两卷,此卷为part1。 《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—...《ACM国际大学生程序设计竞赛:题目与解读》为各类算法配备经典例题及题库,并提供解题思路。
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
《国际大学生程序设计竞赛例题解》是针对ACM(国际大学生程序设计竞赛)和信息学竞赛精心编纂的一份参考资料,尤其适用于广东省大学生程序设计竞赛的参赛者。该资源包含了一系列精选的竞赛题目,旨在帮助参赛者提升...
这个压缩包“国际大学生程序设计竞赛例题解二”显然是一个关于该竞赛的解题集,包含了解决过去竞赛题目的一些策略和方法。 在ICPC中,参赛队伍需要解决一系列复杂的算法问题,在限时内提交正确答案。这些题目通常...
- **国际大学生程序设计竞赛例题解系列**(郭嵩山):提供多种题型的解决方案,帮助学生拓宽解题思路。 - 在线编程平台如ZJU Online Judge、POJ、Codeforces等,提供了丰富的题库供学生练习。 #### 五、训练规范与...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
算法参考资料国际大学生程序设计竞赛例题解数论、计算几何、搜索算法专集
### 国际大学生程序设计竞赛辅导教程知识点概览 #### 一、国际大学生程序设计竞赛简介 - **背景与意义**: - **主办方**:由国际计算机领域历史悠久且颇具权威性的组织——ACM学会(Association for Computer ...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛(ICPC,International Collegiate Programming Contest)是一项全球性的计算机编程赛事,旨在提升大学生的算法设计、问题解决以及团队合作能力。本压缩包“竞赛例题解(六)光盘”包含了该赛事...
本压缩包“国际大学生程序设计竞赛例题解”包含了图论、动态规划以及综合题目的例题解析,是参赛者或对算法感兴趣的学者宝贵的参考资料。 首先,我们来探讨图论这一领域。图论是数学的一个分支,主要研究点(顶点)...
2005年》一书,主要为那些准备参加国际大学生程序设计竞赛(ICPC)以及广东省大学生程序设计竞赛的读者提供了过去竞赛中的一些例题以及解题方法。书中不仅包括了国际赛题,还特别针对广东省的比赛提供了解题资源,...