Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

暴搜N久 依然WA求指教啊~!!

Posted by ans at 2011-03-20 09:55:13 on Problem 1860 and last updated at 2011-03-20 10:01:08
//

#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator