链接：https://ac.nowcoder.com/acm/problem/15108
来源：牛客网
题目描述
随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道，它能不能将他的m个城市在有限的经费内实现公路交通。如果可以的话，输出Yes，否则输出No（两个城市不一定要直接的公路相连，间接公路到达也可以。）
输入描述:
测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0<v1,v2<=m)以及建设公路所需的成本h(h<100)。
输出描述:
对每个测试用例，输出Yes或No。
示例1
输入
20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2
输出
Yes
示例2
输入
10 2 2
1 2 5
1 2 15
输出
Yes
备注:
两个城市之间可能存在多条线路
#include<stdio.h>
int d[100],flag[100],city[100][100];
int main(){
int c,n,m;
int a,b,x;
while (scanf("%d%d%d", &c, &n, &m)!=EOF)
{
while (n--)
{
scanf("%d%d%d",&a,&b,&x);
如果city[a][b]已经不是0，那么这意味着之前已经有一条从a到b的边了。我们此时需要比较已经存储的权重city[a][b]和新读取到的权重x。如果city[a][b]大于x，这意味着我们找到了一条更短的路径，所以我们用x更新city[a][b]的值。如果city[a][b]小于等于x，那么当前这条边不是最短的，所以我们不需要更新权重
city[a][b]=x;
}
}
在这个循环中，d[i]存储了从城市1到城市i的最短路径长度。数组d的初始化值为-1，表示暂时不知道从城市1到其他城市的最短路径。如果城市1直接到城市i有路径（即city[1][i]!=0），那么就将这个路径的长度赋值给d[i]。
for(int i=1;i<=m;i++){
d[i]=-1;//初始化最短路径数组d,-1表示为无穷大
if(city[1][i]!=0){
d[i]=city[1][i];//如果城市1到城市i有路径，则更新最短路径数组d
}
}
flag[1]=1;
for(int i=2;i<=m;i++){
int p=1,min=0;
for(int j=2;j<=m;j++){
if(flag[j]||d[j]==-1){
continue;//如果城市j已经访问了或者没有路径可达则跳过
}
if(d[j]<min||min==0){
min=d[j];//找到未访问的城市中距离最短的
p=j;//记录城市编号
}
}
flag[p]=1;//标记城市p已经被访问了
for(int j=2;j<=m;j++){
if(d[j]!=-1&&d[j]<city[p][j]+d[p]){
d[j]=city[p][j]+d[p];//更新城市p到达其他城市的最短路径
}
}
最后，我们检查从城市1到城市m的最短路径是否不超过预算c：
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
京公网安备 11010502036488号