|
这一题仍然是最短路径,一次AC!好高兴啊。题目是单纯的最短路径的小变形,只要从妈妈说的第二个路口开始找最短路径开始就可以了。
#include <stdio.h>
#define DEBUG 1
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int N=1111 ;
const int Max=0xfffffff ;
int n, sum, map[N][N], dis[N], used[N], mo[30002] ;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Dijstra( )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i, j, index, min ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( i=1; i<=n; ++i ) {
//从第二个路口开始找最短路径,因为,第一个
//路口是必须走的,因为妈妈看着我呢!
dis[i] = map[mo[2]][i] ;
used[i] = 0 ;
}
used[1] = 1 ;
used[mo[2]] = 1 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( i=1; i<=n; ++i ) {
min = Max ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( j=1; j<=n; ++j ) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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] ) ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
#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 ) ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( k=1; k<=sets; ++k ) {
printf("TEST %d ", k ) ;
scanf("%d%d", &n, &r ) ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( i=1; i<=n; ++i ) {
for( j=1; j<=n; ++j )
map[i][j] = Max ;
map[i][i] = 0 ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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 ;
//妈妈说第一条路必须走,因为她说她在看着我
//但是最后还是要减掉的,所以要走,但是不加上。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for( i=2; i<mother; ++i ) {
//如果没路,就输出 N !妈妈和我开玩笑呢!
// 继续下一次读入信息
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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 ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|