当前位置: 代码迷 >> 综合 >> 最短路径 oj
  详细解决方案

最短路径 oj

热度:73   发布时间:2024-01-14 22:51:24.0

最短路径

Time Limit: 1000MS Memory Limit: 65536KB
Problem Description

为了准备一年一度的校赛,大家都在忙着往赛场搬运东西,比如气球什么的。这时 YY 也没有闲着,他也加入了搬运工的行列。已知学校有 N 个路口和 M 条路,YY 并不是把东西直接搬到赛场,而是从 S 路口搬运到 T 路口。由于 YY 非常懒而且他有轻度强迫症。所以他要走的路需要尽可能的短,并且走过路径的数目要为 X 的倍数。

Input

输入的第一行为一个正整数T(1 ≤ T ≤ 20),代表测试数据组数。

对于每组测试数据:

输入的第一行为两个正整数 N 和 M(1 ≤ N ≤ 100, 1 ≤ M ≤ 10000)。

接下来M行每行三个正整数 U、V、W(0 ≤ U, V < N, 0 ≤ W ≤ 230 ),代表有一条从U到V的长度为W的有向路径。

最后一行为三个正整数S、T 、X(0 ≤ S, T < N, 1 ≤ X ≤ 10)。

Output

对于每组测试数据,输出满足条件的从 S 到 T 的最短路径。如果从 S 到 T 不可达,或者无法满足路径数是 X 的倍数,输出“No Answer!”(不包含引号)。

注意:64-bit 整型请使用 long long 来定义,并且使用 %lld 或 cin、cout 来输入输出,请不要使用 __int64 和 %I64d。

Example Input
2
2 1
0 1 1
0 1 2
3 2
0 1 1
1 2 1
0 2 2
Example Output
No Answer!
2
Hint
Author
“师创杯”山东理工大学第五届ACM程序设计竞赛
#include <stdio.h>  
#define MAX 223372036854775807  
long long map[100][100],d[100][10]; //map存图,d存每个点不同情况的状态  
int vi[100][10];    //每个点的各种状态是否遍历过  
void dij(int u,int v,int x,int n)  
{  int i,i1,pos,pos1,x1;  long long t;  for(i=0;n>i;i++)  {  for(i1=0;x>i1;i1++)  {  d[i][i1]=MAX;  vi[i][i1]=0;  }  }  d[u][0]=0;  while(vi[v][0]==0)  {  t=MAX;  pos=-1;  for(i=0;n>i;i++)  {  for(i1=0;x>i1;i1++)  {  if(vi[i][i1]==0&&t>d[i][i1])  {  t=d[i][i1];  pos=i;  pos1=i1;  x1=(i1+1)%x;    //步数记录  }  }  }  if(pos==-1)  {  break;  //起点到终点没有连通  }  vi[pos][pos1]=1;  for(i=0;n>i;i++)  {  if(vi[i][x1]==0&&d[i][x1]>t+map[pos][i])  {  d[i][x1]=t+map[pos][i];  }  }  }  
}  
int main()  
{  int i,t,n,m,i1,i2,u,v,w,x;  scanf("%d",&t);  for(i=1;t>=i;i++)  {  scanf("%d %d",&n,&m);  for(i1=0;n>i1;i1++)  {  for(i2=0;n>i2;i2++)  {  map[i1][i2]=MAX;  }  }  for(i1=1;m>=i1;i1++)  {  scanf("%d %d %d",&u,&v,&w);  if(map[u][v]>w)      //防止重边  {  map[u][v]=w;  }  }  scanf("%d %d %d",&u,&v,&x);  dij(u,v,x,n);       //Dijkstra算法  if(d[v][0]!=MAX)  {  printf("%lld\n",d[v][0]);  }  else  {  printf("No Answer!\n");  }  }  return 0;  
}  

  相关解决方案