题目POJ-1724
题目大意
N个以数字1命名的城市。。。N与单行道相连。每条道路都有两个相关参数:道路长度和道路需要支付的通行费(以硬币数量表示)。
鲍勃和爱丽丝以前住在第一城。鲍勃注意到爱丽丝在他们喜欢玩的纸牌游戏中作弊后,就和她分手了,决定搬到N城去。他想尽快赶到那里,但他手头缺钱。
我们想帮助鲍勃找到从城市1到城市N的最短路径,他可以用他现有的钱负担得起。
输入
输入的第一行包含整数K,0<=K<=10000,这是Bob在路上可以花费的最大硬币数。
第二行包含整数N,2<=N<=100,即城市总数。
第三行包含整数R,1<=R<=10000,即道路总数。
以下R行中的每一行通过指定整数S、D、L和T来描述一条道路,这些整数由单个空白字符分隔:
S为源城市,1<=S<=N
D为目的地城市,1<=D<=N
L是道路长度,1<=L<=100
T是通行费(以硬币数量表示),0<=T<=100
请注意,不同的道路可能具有相同的源城市和目标城市。
输出
输出的第一行和唯一一行应包含从城市1到城市N(其总通行费小于或等于K硬币)的最短路径的总长度。
如果不存在这样的路径,则只应将数字-1写入输出。
思路
很简单的最短路。f[i][j]:从1到i费用为j的最短路。
主要是优化。就是费用>k直接continue
还有第一个到n的一定就是答案。因为状态都合法,是按最短路跑的DP。第一个n遇到就是合法最短路。
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
struct Edge{
int to, w, c, nxt;
}E[10005];
int head[105], cut=0;
void Addedge(int u, int v, int w, int c){
E[++cut]={v, w, c, head[u]}; head[u]=cut;
}
struct Node{
int w, c, u;
bool operator<(const Node& b) const{
return w<b.w;
}
};
priority_queue<Node> q;
int d[105][10005], vis[105][10005];
void getd(int s, int t, int maxc){
memset(d, 0x3f, sizeof(d));
q.push({d[s][0]=0, 0, s});
while(!q.empty()){
int u=q.top().u, us=q.top().c, uw=q.top().w; q.pop();
if(vis[u][us]||us>maxc) continue;//可行优化
if(u==t){//最优优化
printf("%d\n", -uw);
return ;
}
vis[u][us]=1;
for(int i=head[u]; i; i=E[i].nxt){
int to=E[i].to, w=E[i].w, c=E[i].c;
if(!vis[to][us]&&d[to][us+c]>d[u][us]+w){
d[to][us+c]=d[u][us]+w;
q.push({-d[to][us+c], us+c, to});
}
}
}
}
int main() {
int k; scanf("%d", &k);
int n, m; scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++){
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
Addedge(a, b, c, d);
}
getd(1, n, k);
return 0;
}