ccf20160904交通规划 不知道错哪了 求数据 求查错

Question

#include
#include
#include
#include
#include
using namespace std;
int ll[1001][1001];
struct node
{
int per;
int sumlen;
bool vis;
node() :per(0), sumlen(0),vis(0) {};
};
node dd[1001];
int dijikstra(int s,int n)
{
int i,sum = 0,j, min,count=0;
while (count < n-1)
{
min = 1 << 30;
dd[s].vis = 1;//s为每次可能替换成的前驱
for (i = 1; i <= n; i++)
{
if (ll[s][i]>0&& !dd[i].vis)//次节点的前驱可修改
{
if (!dd[i].per)//没有前驱
{
dd[i].per = s;
dd[i].sumlen += ll[s][i]+dd[s].sumlen;
}
else//已有前驱 判断是否变动
{
if (dd[i].sumlen > dd[s].sumlen + ll[i][s])
{
dd[i].per = s;
dd[i].sumlen = dd[s].sumlen + ll[i][s];
}
else if (dd[i].sumlen == dd[s].sumlen + ll[i][s])//注意我们要求的是最短公路
{
if (ll[i][dd[i].per] > ll[i][s])
{
dd[i].per = s;
dd[i].sumlen = dd[s].sumlen + ll[i][s];
}
}
}
}
if (!dd[i].vis&&dd[i].sumlen&&min >=dd[i].sumlen)//min记录每次最短公路
{
if (min == dd[i].sumlen)
{
if (ll[dd[j].per][j] > ll[dd[i].per][i])
{
min = dd[i].sumlen;
j = i;
}
}
else
{
min = dd[i].sumlen;
j = i;
}
}
}
s = j;
sum += ll[dd[j].per][j];
count++;
}
return sum;
}
int main()
{
memset(ll,-1,sizeof(ll));
int n, m; cin >> n >> m;
//n = 4; m = 5;
int i, a, b, c;
for (i = 1; i <= n; i++)
ll[i][i] = 0;
for (i = 0; i < m; i++)
{
cin >> a >> b >> c;
ll[a][b] = ll[b][a] = c;
}
/*ll[1][2] = ll[2][1] = 4;
ll[1][3] = ll[3][1] = 5;
ll[2][3] = ll[3][2] = 2;
ll[2][4] = ll[4][2] = 3;
ll[3][4] = ll[4][3] = 2;*/
cout << dijikstra(1, n) << endl;
return 0;
}

Answer 1

http://blog.csdn.net/moilk_nepho/article/details/52950546