第1题     城市规划 查看测评数据信息
有n个城市，依次编号为1，2.......n，另外有一个文件保存n个城市之间的距离。当两个城市的距离等于-1时，表示这两个城市间没有直接铁路相通。编程实现：把哪条铁路的长度减半，能使得城市1到城市n的最短距离下降的最多。

输入格式
第一行有一个数：n(n<=50)，以下是矩阵，表示城市之间的距离。距离a[i,j]<=127

输出格式
三行，第一行输出距离减半的两个顶点，用一个空格隔开。 
第二行为1到n的最短距离,保留1位小数。 
第三行输出经过城市编号，用一个空格隔开，注意最后不要有空格 

输入/输出例子1
输入：

5
0 40 65 -1 30
40 0 105 -1 -1
65 105 0 10 35
-1 -1 10 0 20
30 -1 35 20 0


输出：

1 5
15.0
1 5


样例解释
无

然后是本人爆0程序：

#include<bits/stdc++.h>
using namespace std;
double a[60][60],dis[60],ma;
long long road[60],cnt,n,visit[60],sc[60],x,y;
void dij() {
	for(int i=1;i<=n;i++) {
		dis[i]=INT_MAX;
		visit[i]=0;
	}
	dis[1]=0;
	for(int i=1;i<=n;i++) {
		int p=0,min=INT_MAX;
		for(int j=1;j<=n;j++)
			if(dis[j]<min&&visit[j]==0) p=j,min=dis[j];
		if(p==0) break;
		for(int j=1;j<=n;j++) 	if(dis[p]+a[p][j]<dis[j]) dis[j]=dis[p]+a[p][j],road[j]=p;
	}
}
void find(int x){
	if(visit[x]==0) sc[++cnt]=1;
	else find(visit[x]);
	sc[++cnt]=x;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			cin>>a[i][j];
			if(a[i][j]==-1) a[i][j]=INT_MAX;
		}
	}
	dij();
	find(n);
	for(int i=2;i<=cnt;i++) {
		if(a[sc[i-1]][sc[i]]>ma) {
			ma=a[sc[i-1]][sc[i]];
			x=sc[i-1];
			y=sc[i];
		}
	} 
	cout<<x<<" "<<y<<endl;
	printf("%.1lf\n",dis[n]-ma/2);
	for(int i=1;i<cnt;i++) cout<<sc[i]<<" ";
	cout<<sc[cnt];
 	return 0;
}

用的是Dijkstra算法