去长沙理工考ccf。恰好又可以见闺蜜。
前2道题很简单，第三题题目太长就跳过了【绕来绕去就像“你儿子是我儿子的爸爸一样头疼”】，就做第四题。但是还有最后一个部分没写写好就到点了。
现在把它补充完整。
我忘记怎么在函数参数中使用二维数组，所以直接把函数写在main里。
分为2个部分，一个是求最短路径，一个是找出要改建的路。
最短路径采用的是dijkstra算法。
寻找要改建的路的部分。我一开始一直想要使用最小支撑树实现【即贪心算法】。但是我后来恍然发现，最后一个状态一定是每个城市都能以最短路径达到首都。那么a城市的最短路径就是与a相邻的某一个城市b的最短路径加上ab城市的距离。
需要说明的是，我没有使用大量数据测试。
仅供参考，如有错误，欢迎指正，共同学习。
#include<iostream>
#define far 1000
using namespace std;
int main()
{
int n,m,i,j,k;
int sum=;
int x,y,z;
cin>>n>>m;
int a[n][n],edge[m];
int visit[n],dis[n];
for(i=;i<n;i++)
{
for(j=;j<n;j++)
{
a[i][j]=far;
}
visit[i]=;
dis[i]=far;
}
for(i=;i<m;i++)
{
cin>>x>>y>>z;
a[x-][y-]=a[y-][x-]=z;
edge[i]=z;
}
for(i=;i<n;i++)
{
for(j=;j<n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
dis[]=;
int v;
for(i=;i<n;i++)
{
for(j=;j<n;j++)
{
if(visit[j]==&&dis[j]!=far)
v=j;
}
for(j++;j<n;j++)
{
if((visit[j]==)&&(dis[j]<v))
v=j;
}
visit[v]=;
for(j=;j<n;j++)
{
if(dis[j]>dis[v]+a[v][j])
dis[j]=dis[v]+a[v][j];
} }
for(j=;j<n;j++)
cout<<dis[j]<<" ";
cout<<endl; for(i=;i<n;i++)
visit[i]=; visit[]=;
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
if(edge[j]==dis[i])
{
cout<<"改变的边--"<<edge[j]<<endl;
sum=sum+edge[j];
edge[j]=;
visit[i]=;
}
}
}
for(i=;i<n;i++)
{
if(visit[i]==)
{
for(j=;j<n;j++)
{
if(dis[j]+a[i][j]==dis[i])
{
for(int k=;k<m;k++)
{
if(edge[k]==a[i][j])
{
cout<<"改变的边--"<<edge[k]<<endl;
sum=sum+edge[k];
edge[k]=;
visit[i]=;
break;
}
}
}
}
}
}
cout<<endl<<"sum---"<<sum<<endl;
cout<<"visit"<<endl;
for(i=;i<n;i++)
cout<<visit[i]<<" ";
return ; }
因为没有注释，可能比较难看懂。不懂的地方，也欢迎和我交流。