| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
WA了很多次,不知道是什么问题,在这里发代码,路人请指教#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
#include <queue>
#define fillary(x,y,z) (fill_n(&(y),sizeof(x)/sizeof(y),(z)))
using namespace std;
//存储某个点的序号,以及到源点的当前最短路径
class VnD {
public:
int i, d;
VnD(){}
VnD(int ii, int dd) :i(ii), d(dd){}
bool operator < (const VnD& a) const {
return d > a.d;
}
};
int N, A, B;
int g[200][200]; //图的临接矩阵
int d[200]; //某个点的最短路径的上界
bool sure[200]; //记录某个点的最短路径是否已经被确定
priority_queue<VnD> T; //临时点集合
const int BIGGEST = 9999999;
void input() {
scanf("%d %d %d", &N, &A, &B);
int i;
fillary(g, g[0][0], BIGGEST);
for (i = 1; i <= N; i++) {
int j, k, id;
scanf("%d", &j);
for (k = 1; k <= j; k++) {
scanf("%d", &id);
if (k==1) {
g[i][id] = 0;
}
else {
g[i][id] = 1;
}
}
}
}
int main() {
input();
fillary(sure, sure[0], false);
fillary(d, d[0], BIGGEST);
d[A] = 0;
while(!T.empty())T.pop();
int i;
for (i = 1; i <= N; i++) {
T.push( VnD(i, d[i]) );
}
int cur;
int tmp;
while (!T.empty() && !sure[B]) {
cur = T.top().i;
T.pop();
if (sure[cur]) continue;
sure[cur] = true;
for (i = 1; i <= N; i++) {
if (g[cur][i] == BIGGEST) continue;
tmp = d[cur] + g[cur][i];
if ( tmp < d[i]) {
d[i]= tmp;
T.push( VnD(i, d[i]) );
}
}
}
if (sure[B]) printf("%d\n", d[B]);
else printf("-1\n");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator