|
|
這一題仍然是最短路徑，一次AC！好高興啊。題目是單純的最短路徑的小變形，只要從媽媽說的第二個(gè)路口開始找最短路徑開始就可以了。
 #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 ){
//從第二個(gè)路口開始找最短路徑，因?yàn)椋谝粋€(gè)
//路口是必須走的，因?yàn)閶寢尶粗夷兀?nbsp;
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] ;
}
//計(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 ;
//媽媽說第一條路必須走，因?yàn)樗f她在看著我
//但是最后還是要減掉的，所以要走，但是不加上。
for( i=2; i<mother; ++i ){
//如果沒路，就輸出 N ！媽媽和我開玩笑呢！
// 繼續(xù)下一次讀入信息
if( map[mo[i]][mo[i+1]] == Max ){
printf("N\n") ;
flag = 1 ;
break ;
}
//按照媽媽說的路線走，看看要走多遠(yuǎn)
sum += map[mo[i]][mo[i+1]] ;
}
if( !flag )
Dijstra( ) ;
}
return 0 ;
}
|