2020.2.22普及C组模拟赛9(第二题)
2.【普及模拟】城市连接
题目描述
天网恢恢,疏而不漏,经过上一次的抓捕,OI总部终于获取了怪盗的特征!现在,我们需要在基德再次来之前就把他的特征送到超级大牛的手上,可惜超级大牛不在总部,所以飞过海必须尽快把资料送到大牛家里。已知OI总部到大牛家中间有n-2个城城市,为了尽快达到目的地,飞过海通过水晶球了解到OI总部到大牛家的路线图,图上显示了n个城之间的连接距离。
可是飞过海很忙,需要请你来帮忙编写一个程序。
输入
输入文件中的第一行为一个整数n(n<=1000)。
第二行至第n+1行,每行有n个数。其中:第i+1行中表示第i个城市与其他城市之间的连接关系,0表示不连接,其它数字表示连接的距离。
输出
输出文件中的第一行为n个整数,表示所选的线路。
第二行中为一个数,表示最短距离。
样例输入
7
0 3 5 0 0 0 0
0 0 0 7 8 6 0
0 0 0 0 4 5 0
0 0 0 0 0 0 4
0 0 0 0 0 0 7
0 0 0 0 0 0 6
0 0 0 0 0 0 0
样例输出
1 2 4 7
14
正解
用Dijkstra模板就OK了,记住记录好路径,用递归输出路径
Dijkstra
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,k,m,v[1005],d[1005],b[1005],a[1005][1005];
void dg(int x)//递归输出路径
{
if(b[x]!=0)dg(b[x]);
printf("%d ",x);
}
int main()
{
//freopen("city.in","r",stdin);
//freopen("city.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)//赋值
if(a[1][i]!=0){
d[i]=a[1][i];b[i]=1;}else d[i]=2147483647;
v[1]=1;//标记
for(int i=1;i<=n;i++)//下面是模板
{
m=2147483647;
for(int j=1;j<=n;j++)
if(v[j]==0&&d[j]<m)
{
k=j;
m=d[j];
}
v[k]=1;
for(int j=1;j<=n;j++)
if(v[j]==0&&d[k]+a[k][j]<d[j]&&a[k][j]!=0)
{
d[j]=d[k]+a[k][j];
b[j]=k;
}
}
dg(n);
cout<<endl<<d[n];
return 0;
}
下面附本次比赛的其他题目
2020.2.22普及C组模拟赛9(第一题)
2020.2.22普及C组模拟赛9(第二题)
2020.2.22普及C组模拟赛9(第三题)
2020.2.22普及C组模拟赛9(第四题)
2020.2.22普及C组模拟赛9(总结)