1724.txt

北京大学的一些acm代码。还有一些资料。

1724 roads的代码：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 101;
struct Node {int x, w, f; void set(int xx, int ww, int ff) {x = xx; w = ww; f = ff;} };
vector<Node> adj[N][N];
int money, nv, ne;

bool operator<(const Node& a, const Node& b) { return a.w > b.w; }

void solve() {
int x, i, j, y;
priority_queue<Node> pq;
Node now, cur;
now.set(0, 0, 0);
pq.push(now);
while(!pq.empty()) {
cur = pq.top();
pq.pop();
x = cur.x;
if(x == nv-1) {
printf("%d\n", cur.w);
return;
}
for(i = 0; i < nv; ++i) {
for(j = 0; j < adj[x][i].size(); j++) if(cur.f + adj[x][i][j].f <= money) {
y = adj[x][i][j].x;
now.set(y, cur.w + adj[x][i][j].w, cur.f + adj[x][i][j].f);
pq.push(now);
}
}
}
printf("-1\n");
}

int main() {
int i, u, v, w, f;
Node now;
scanf("%d %d %d", &money, &nv, &ne);
for(i = 0; i < ne; ++i) {
scanf("%d %d %d %d", &u, &v, &w, &f); 
--u; --v;
now.set(v, w, f);
adj[u][v].push_back(now);
}

solve();

return 0;
}