讨论 / 应该是Shortest Path啦,怎么会是MST呢?
飞雪天涯 2008-10-29 08:05:00
点我顶贴 收藏 删除
#include<cstdio>

using namespace std;

const int MAX = 1001;

const int INF = 1000000;

int d[MAX];

int c[MAX][MAX];

bool flag[MAX];

//int path[MAX];

int Dijkstra(int beg, int n)

{

int i, j, u, tmp;

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

{

d[i] = c[beg][i];

flag[i] = false;

}

d[beg] = 0; flag[beg] = true;

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

{

tmp = INF; u = beg;

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

{

if(!flag[j] && d[j] < tmp)

{

u = j;

tmp = d[j];

}

}

flag[u] = true;

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

{

if(!flag[j] && c[u][j] < INF)

{

if(d[u] + c[u][j] < d[j])

d[j] = d[u] + c[u][j];

//path[j] = u;

}

}

}

return 0;

}

int main()

{

int n;scanf("%d",&n);

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++){

scanf ("%d",&c[i][j]);

if(c[i][j]==0)c[i][j]=INF;

}

Dijkstra(1,n);

printf("%d ",d[n]*(n+1));

printf("%d",d[n]);

while(1);

return 0;

}

查看更多回复
提交回复