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