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 |
暴搜N久 依然WA求指教啊~!!// #include<cstdio> #include<cstring> #include <cstdlib> #include <vector> #include <queue> #define CLR(a) memset((a),0,sizeof((a))) #define esp 1e-8 using namespace std; const int maxn = 500; struct point { int dest; double rate; double fee; }; double dis[maxn]; vector<point> gph[maxn]; int solve(int s, double v) {//从S开始广搜 queue<int> que; CLR(dis); dis[s] = v; que.push(s); while (!que.empty()) { int cur = que.front(); que.pop(); for (int i = 0; i < gph[cur].size(); i++) { double next = (dis[cur] - gph[cur][i].fee) * gph[cur][i].rate; if (next > dis[gph[cur][i].dest] + esp) {//只搜距离变长了的点 dis[gph[cur][i].dest] = next;//更新距离 que.push(gph[cur][i].dest); if (gph[cur][i].dest == 1)//死搜直到回到S return 1; } } } return 0; } int main() { int n, m, s; double v; while (~scanf("%d%d%d%lf", &n, &m, &s, &v)) { int i; for (i = 1; i <= n; i++) gph[i].clear(); for (i = 0; i < m; i++) { point tmp, tmp1; scanf("%d%d", &tmp1.dest, &tmp.dest); scanf("%lf%lf%lf%lf", &tmp.rate, &tmp.fee, &tmp1.rate, &tmp1.fee); gph[tmp1.dest].push_back(tmp); gph[tmp.dest].push_back(tmp1); } if (solve(s, v)) printf("YES\n"); else printf("NO\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