讨论 / Floyd O(n3)
lqybzx 2013-11-05 20:46:29
点我顶贴 收藏 删除
#include <cstdio>

#include <iostream>

using namespace std;

int n, i, j, k, l, m, s, be, en, j1, j2;

int a[200+1][200+1], v1[200+1][200+1];

bool v[200+1];

int dist[200+1], b[200+1];

int main()

{

cin >> n >> m >> k >> be >> en;

for (i=1; i<=n; i++) cin >> b[i];

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

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

cin >> v1[i][j];

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

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

a[i][j] = 10000000;

for (i=1; i<=k; i++) {

cin >> j >> j1 >> j2;

a[j][j1] = j2;

a[j1][j] = j2;

if (v1[b[j]][b[j1]]==1) a[j1][j] = 10000000;

if (v1[b[j1]][b[j]]==1) a[j][j1] = 10000000;

}

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

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

if (b[i]==b[j]) {

a[i][j] = 10000000;

a[j][i] = 10000000;

}

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

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

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

if (i!=j && i!=k && j!=k)

if (a[i][k]+a[k][j]<a[i][j])

a[i][j] = a[i][k] + a[k][j];

v[1] = true;

dist[be] = 0;

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

dist[i] = 10000000;

v[i] = false;

}

if (a[be][en]>=10000000 || b[be]==b[en])

cout <<"-1" << endl;

else

cout << a[be][en] << endl;

return 0;

}

#1 董阴@2014-01-25 00:06:45
回复 删除
我这傻X居然调用n次Dijkstra。。。这复杂度啊!
查看更多回复
提交回复