1195: V8与女友
时间限制: 1 Sec 内存限制: 128 MB
提交: 1244 解决: 257
[提交][状态][讨论版]
题目描述
那是遥远的公元前2333年，V8还有女朋友的时代。
他和他的女友分别是两个距离遥远的部落的首领，那时候没有现在发达的交通工具和路网，V8每次希望团圆的时候，都要跋山涉水不远万里去会见他的爱人，辛酸的很。经过很多次的旅途，V8掌握了他可以走的所有的路的路线图，毕竟作为首领，不能离开自己的领地太久，所以V8希望你给他找出一条最近的路，并且输出一次往返所需要的最短时间，V8并不会在对方领地停留，说个你好就回来了，需要的时间为0。
虽然不管你求出来有多快，最终V8还是觉得自己在路上花费的时间太多，选择了舍小家而为大家（手动滑稽。
输入
第一行一个正整数t，表示数据的组数（t <=10）。
之后对于每组数据，第一行一个正整数k，表示这个地图（无向图）的路径数（k<=10000）。
之后有k行，每一行三个正整数，s，t，v。表示路的两个端点和这条路需要的时间（s,t,v <=100）。
第k+1行为两个数，v,m，表示V8和他爱人的所在地。
输出
对于每组数据，输出一行一个正整数，为V8一个来回最短的时间（数据保证有通路）。
样例输入
1
4
1 2 1
1 3 1
2 4 2
3 4 1
1 4
样例输出
4
提示
来源
fpc
#include<stdio.h>
#include<math.h>
#include<string.h>
#define max(a,b) (a>b)? b:a
#define MAX 101
#define INF 1000000000
int dijkstra (int mat[][MAX],int n, int s,int f)
{
//s为起点， f：为终点 int dis[MAX];//记录到任意点的最短距离 int mark[MAX];//记录被选中的结点 int i,j,k = 0; for(i = 0 ; i < n ; i++)//初始化所有结点，每个结点都没有被选中 mark[i] = 0; for(i = 0 ; i < n ; i++)//将每个结点到start结点weight记录为当前distance { dis[i] = mat[s][i]; //path[i] = s; } mark[s] = 1;//start结点被选中 //path[s] = 0; dis[s] = 0;//将start结点的的距离设置为0 int min ;//设置最短的距离。 for(i = 1 ; i < n; i++) { min = INF; for(j = 0 ; j < n;j++) { if(mark[j] == 0 && dis[j] < min)//未被选中的结点中，距离最短的被选中 { min = dis[j] ; k = j; } } mark[k] = 1;//标记为被选中 for(j = 0 ; j < n ; j++) { if( mark[j] == 0 && (dis[j] > (dis[k] + mat[k][j])))//修改剩余结点的最短距离 { dis[j] = dis[k] + mat[k][j]; } } } return dis[f];
}
int mat[MAX][MAX];
int main()
{ int t;scanf("%d",&t);while(t--){int n=MAX,m; scanf("%d",&m); //n是节点个数 int a,b,dis; if(m == 0) break; int i,j; for(i = 0 ; i < MAX;i++) for(j = 0 ; j < MAX; j++) mat[i][j] = INF; for(i = 0 ; i < m ;i++) //接受m行数据 { scanf("%d %d %d",&a,&b,&dis); --a,--b; if(dis < mat[a][b] || dis < mat[b][a]) mat[a][b] = mat[b][a] = dis; } int s,t;scanf("%d %d",&s,&t);s--;t--;int ans = dijkstra(mat,n,s,t); ans=2*ans;printf("%d\n",ans); } return 0;
}