原题：http://acm.hdu.edu.cn/showproblem.php?pid=2066
本人写的 至今还不知道为什么 WA 0rz！
//HDU 2066
#include <iostream>
using namespace std;
const int MAX = 1002;
const int INF = 0x7FFFFFF;//4字节int最大值
int g[MAX+1][MAX+1];//存储图
int hash[MAX+1];//存储是否访问
int path[MAX+1];//存储从源到i的最短路径，及特殊路径
int T , S , D , L;
int s[MAX];
int d[MAX];
#define min(a,b) a>b?b:a
#define max(a,b) a>b?a:b
int Dijkstra ( int beg , int end ) //Dijkstra算法，求beg到end的最短路径长
{
path[beg] = 0;
hash[beg] = false;//源点访问
while ( beg != end )
{
int m = INF, temp;
for ( int i = 0; i <= L+1; ++ i )
{
if ( g[beg][i] != INF )
path[i] = min ( path[i], path[beg] + g[beg][i] );
if ( m > path[i] && hash[i] )
{
m = path[i];
temp = i;
}
}
beg = temp;
if ( m == INF )
break;
hash[beg] = false;
}
if ( path[end] == INF )
return -1;
return path[end];
}
int main()
{
int i , a , b , time ;
while(cin>>T>>S>>D)
{
L = 0;
for (i = 0; i != MAX; ++ i )
{
hash[i] = true;
path[i] = INF;
for ( int j = 0; j < MAX; ++ j )
{
g[i][j] = INF;
}
}
for(i=0; i<T; i++)
{
cin>>a>>b>>time;
if(time < g[a][b])
g[a][b] = g[b][a] = time;
if(L < max(a,b))
L = max(a,b);
}
for(i=1 ; i<=S; i++)
{
cin>>s[i];
g[0][s[i]] = g[s[i]][0] = 0;
}
for(i=1 ; i<=D; i++)
{
cin>>d[i];
g[d[i]][L+1] = g[L+1][d[i]] = 0;
}
cout<<Dijkstra(0,L)<<endl;
}
return 0;
}
一个思路 AC的代码：
#include <iostream>
using namespace std;
const int INF = 0x7FFFFFFF;
int T,S,D,L;
const int MAXN=1005; //点个数
int graph[MAXN][MAXN];
int s[MAXN];
int d[MAXN];
int Dijkstra ( int beg, int end )
{
bool hash[MAXN];
int path[MAXN];
for ( int i = 0; i <= L; ++ i )
{
hash[i] = true;
path[i] = INF;
}
hash[beg] = false;
path[beg] = 0;
while ( beg != end )
{
for ( int i = 0; i <= L; ++ i )
{
if ( graph[beg][i] != 0 )
{
if ( path[i] > path[beg] + graph[beg][i] )
path[i] = path[beg] + graph[beg][i];
}
}
int min = INF;
for ( int i = 0; i <= L; ++ i )
{
if ( min > path[i] && hash[i] )
{
min = path[i];
beg = i;
}
}
hash[beg] = false;
}
return path[end];
}
int main ()
{
while ( scanf ( "%d%d%d",&T,&S,&D ) != EOF )
{
memset ( graph , 0 , sizeof ( graph ) );
L = 0;
for ( int i = 1; i <= T; ++ i )
{
int r,c,cost;
scanf ( "%d%d%d",&r,&c,&cost );
if ( graph[r][c] == 0 )
graph[r][c] = graph[c][r] = cost ;
else
{
if ( cost < graph[r][c] )
graph[r][c] = graph[c][r] = cost ;
}
if ( L < max ( r,c ) )
L = max ( r,c );
}
for ( int i = 0; i != S; ++ i )
{
scanf ( "%d",&s[i] );
graph[0][ s[i] ] = 1;
graph[ s[i] ][0] = 1;
}
L ++;
for ( int i = 0; i != D; ++ i )
{
scanf ( "%d",&d[i] );
graph[ d[i] ][ L ] = 1;
graph[ L ][ d[i] ] = 1;
}
cout << Dijkstra ( 0,L ) - 2 << endl;
}
return 0;
}
NB 大神 的邻接表 0ms 代码：
#include <iostream>
#define MAX 1005
#define INF 0x7FFF
#define CMP(A,B) (A.d < B.d)
using namespace std;
int d[MAX][MAX];
class HNode {
public:
int v;
int d;
};
class Heap {
public:
HNode h[MAX * 2];
int n, p, c;
Heap() {
n = 0;
}
void inline ins(HNode e) {
for (p = ++n; p > 1 && CMP(e,h[p>>1]); h[p] = h[p>>1], p >>= 1)
;
h[p] = e;
}
int inline pop(HNode &e) {
if (!n)
return 0;
for (e = h[p = 1], c = 2; c < n
&& CMP(h[c += (CMP(h[c + 1],h[c]) && c < n - 1)], h[n]);
h[p] = h[c], p = c, c <<= 1)
;
h[p] = h[n--];
return 1;
}
};
int Dijkstra(int A, int B, int N) {
int dist[MAX];
int mask[MAX];
int Tmp;
Heap h;
HNode e, ne;
for (int i = 0; i < N; i++) {
dist[i] = INF;
mask[i] = 0;
}
dist[e.v = A] = (e.d = 0);
h.ins(e);
while (h.pop(e)) {
if (!mask[e.v]) {
mask[e.v] = 1;
for (int i = 0; i < N; i++) {
if (!mask[i] && (Tmp = e.d + d[e.v][i])
< dist[i]) {
dist[ne.v = i] = (ne.d = Tmp);
h.ins(ne);
}
}
}
}
return dist[B];
}
int main() {
int T, S, D, M;
int st, en, tm;
while (scanf("%d %d %d", &T, &S, &D)!=EOF) {
M = 0;
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
d[i][j] = INF;
for (int i = 0; i < T; i++) {
scanf("%d %d %d", &st, &en, &tm);
if (tm < d[st][en]) {
d[st][en] = d[en][st] = tm;
}
M = st> M ? st : M;
M = en> M ? en : M;
}
M = M + 1;
for (int i = 0; i < S; i++) {
scanf("%d", &st);
d[0][st] = 1;
d[st][0] = 1;
}
for (int i = 0; i < D; i++) {
scanf("%d", &en);
d[M][en] = 1;
d[en][M] = 1;
}
cout<<Dijkstra(0, M, M+1)-2<<endl;
}
return 0;
}