| ||||||||||
| 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