文章结束给大家来个程序员笑话：[M]
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=53
http://poj.org/problem?id=1122
整体来说，仍然是Dijkstra的模版题，但是还是有很大变通，又锤炼了思维，不至于思维当初就固化了；
而且须要特判；
题意为：输入case组数据（zoj有 , poj没有 ，然后再输入一个N，代表有N条路，然后就是N * N 的矩阵图，代表各段路之间的距离，当为-1时，代表此路不通；然后输出END代表末了（本来按照模版是起始点，但是由于后面还要输入多组数据作为起点），接着输入多组start;
须要求得就是最短路径和记录路径；
但是输出时有要求：
按照最短路径从小到大排序，然后分离输出起始点（即start点 ），终点（end),最短路，输出路径。
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std ;
const int INF = 1000000 ;
const int maxn = 20 ;
int n ;
int edge[ maxn ][ maxn ] ;
int S[ maxn ] ;
int dist[ maxn ] ;
int path[ maxn ] ;
int end;
/*typedef struct Fire
{
int street[MAX], len, start, E;
bool operator < (const Fire &other) const
{
return len < other.len;
}
}Fire;
Fire fire[MAX];*/
struct Fire
{
int street[ maxn] , len ,start , E ;
bool operator < ( const Fire other )const
{
return len < other.len ;
}
}fire[ maxn ];
int cmp( const void *x , const void *y )
{
return *(int *)x < *(int *)y ;
}
void Dijkstra( int v0 , Fire &su)
{
int i , j , k ;
for( i = 1 ; i <= n ; i++ )
{
dist[ i ] = edge[ v0 ][ i ] ;
S[ i ] = 0 ;
if( i != v0 && dist[ i ] < INF )
path[ i ] = v0 ;
else
path[ i ] = -1 ;
}
S[ v0 ] = 1 ;
dist[ v0 ] = 0 ;
path[ v0 ] = -1 ;
for( i = 1 ; i <= n - 1 ; i++ )
{
int MIN = INF , u = v0 ;
for( j = 1 ; j <= n ; j++ )
{
if( !S[ j ] && dist[ j ] < MIN )
{
u = j ;
MIN = dist[ j ] ;
}
}
S[ u ] = 1 ;
for( k = 1 ; k <= n ; k++ )
{
if( !S[ k ]&& edge[ u ][ k ] < INF && dist[ u ] + edge[ u ][ k ] < dist[ k ] )
{
dist[ k ] = dist[ u ] + edge[ u ][ k ] ;
path[ k ] = u ;
}
}
if( u == end)
break;
}
k = 0 ;
su.street[ k ] = end ;
int ho = path[ end ] ;
while( ho != -1 )
{
su.street[ ++k ] = ho;
ho = path[ ho ] ;
}
su.E = k ;
su.len = dist[ end ] ;
}
/* k = 0;
su.street[k] = end;
int ho = path[end];
while (ho != -1)
{
su.street[++k] = ho;
ho = path[ho];
}
su.E = k;
su.len = dist[end];
}*/
int main()
{
int i , j ;
int Case ;
scanf( "%d" , &Case );
while( Case-- )
{
scanf( "%d" , &n ) ;
memset( edge , 0 , sizeof( edge ) ) ;
for( i = 1 ; i <= n ; i++ )
{
for( j = 1 ; j <= n ; j++ )
{
scanf( "%d" , &edge[ i ][ j ] ) ;
if( edge[ i ][ j ] == -1 )
edge[ i ][ j ] = INF ;
}
}
scanf( "%d" , &end ) ;
printf("Org\tDest\tTime\tPath\n");
int cnt = 0 , start ;
while( ~scanf( "%d" , &start ) )
{
fire[ cnt ].start = start ;
Dijkstra(start,fire[cnt]);
cnt++ ;
}
sort( fire ,fire + cnt ) ;
for( i = 0 ; i < cnt ; i++ )
{
printf( "%d\t%d\t%d\t" , fire[ i ].start ,end , fire[ i ].len ) ;
for( j = fire[ i ].E ; j > 0 ; --j )
{
printf( "%d\t" , fire[ i ].street[ j ] ) ;
}
printf( "%d\n" , fire[ i ].street[ 0 ] ) ;
}
}
return 0 ;
}
文章结束给大家分享下程序员的一些笑话语录： 这年头的互联网真是娱乐了中国，网民们从各种各样的“门”里钻来钻去，又有好多“哥”好多“帝”，值得大家品味不已……网络经典语录，关于IT与互联网，经典与您分享！