杭电 2544 ，求差错，勿贴代码，谢谢！！！！

显示全部楼层 · 2011-3-13 10:41:11

#include iostream
#define MAX_VALUE 110
#define MAX 65535
using namespace std;
int path[MAX_VALUE][MAX_VALUE];
int destin[MAX_VALUE];
bool flag[MAX_VALUE];
int main()
{

int m,n;

int i,j;

int a,b,c;

int min,mind;

while(cinnm)

{

if(m == 0

for( i = 0; iMAX_VALUE; i)

for( j = 0; jMAX_VALUE; j)

path[j] = MAX;

for( i = 0; im; i)

{

cinabc;

path[a] = path[a] = c;

}

for( i = 1; i=n; i)

{

destin = path[n];

}

for( i = 1; i=n; i)

flag = 0;

flag[n] = 1;

for( i = 1; i=n; i)

{

min = MAX;

for( j = 1; j=n; j)

{

if(!flag[j])

{

if(destin[j]min)

{

min = destin[j];

mind = j;

}

}

}

flag[mind] = 1;

for( j = 1; j=n; j)

{

if(!flag[j]destin[j])

{

destin[j] = path[mind][j] min;

}

}

}

coutdestin[1]endl;

}

return 0;
}

千问 · 2011-3-13 10:41:11

<pre id=\"best-answer-content\" class=\"reply-text mb10\">不是求最短时间吗？

if(!flag[j]destin[j])//有问题吧，我感觉应该用小于号

{

destin[j] = path[mind][j] min;

}
已在杭电ACM上测试过了，C通过。
path[mind][j] min是你新找到的路径，如果path[mind][j] min小于destin[j]（以前保存的最短路径），那么就可以destin[j] = path[mind][j] min;destin[j] 就保存当前的最短路径。