|
|
这一题仍然是最短路径，一次AC！好高兴啊。题目是单纯的最短路径的小变形，只要从妈妈说的第二个路口开始找最短路径开始就可以了。
 #include <stdio.h>
#define DEBUG 1
const int N=1111 ;
const int Max=0xfffffff ;
int n, sum, map[N][N], dis[N], used[N], mo[30002] ;
void Dijstra( )
   {
 int i, j, index, min ;
  for( i=1; i<=n; ++i ){
//从第二个路口开始找最短路径，因为，第一个
//路口是必须走的，因为妈妈看着我呢！
dis[i] = map[mo[2]][i] ;
used[i] = 0 ;
 }
used[1] = 1 ;
used[mo[2]] = 1 ;
for( i=1; i<=n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
for( j=1; j<=n; ++j )
if( !used[j] && dis[j] > dis[index]+map[index][j] )
dis[j] = dis[index]+map[index][j] ;
}
//计算差值
printf("Y %d\n", sum-dis[n] ) ;
 }
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
#endif
int i, j, k, r, di, flag, x, y, sets, mother ;
scanf("%d", &sets ) ;
for( k=1; k<=sets; ++k ){
printf("TEST %d ", k ) ;
scanf("%d%d", &n, &r ) ;
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j )
map[i][j] = Max ;
map[i][i] = 0 ;
}
for( i=1; i<=r; ++i ){
scanf("%d%d%d", &x, &y, &di ) ;
map[x][y] = map[y][x] = di ;
}
scanf("%d", &mother ) ;
for( i=1; i<=mother; ++i )
scanf("%d", &mo[i] ) ;
sum = flag = 0 ;
//妈妈说第一条路必须走，因为她说她在看着我
//但是最后还是要减掉的，所以要走，但是不加上。
for( i=2; i<mother; ++i ){
//如果没路，就输出 N ！妈妈和我开玩笑呢！
// 继续下一次读入信息
if( map[mo[i]][mo[i+1]] == Max ){
printf("N\n") ;
flag = 1 ;
break ;
}
//按照妈妈说的路线走，看看要走多远
sum += map[mo[i]][mo[i+1]] ;
}
if( !flag )
Dijstra( ) ;
}
return 0 ;
}
|