ROADS
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 8734 | Accepted: 3244 |
Description
N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins).
Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash.
We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash.
We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
Input
The first line of the input contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way.
The second line contains the integer N, 2 <= N <= 100, the total number of cities.
The third line contains the integer R, 1 <= R <= 10000, the total number of roads.
Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters :
Notice that different roads may have the same source and destination cities.
The second line contains the integer N, 2 <= N <= 100, the total number of cities.
The third line contains the integer R, 1 <= R <= 10000, the total number of roads.
Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters :
- S is the source city, 1 <= S <= N
- D is the destination city, 1 <= D <= N
- L is the road length, 1 <= L <= 100
- T is the toll (expressed in the number of coins), 0 <= T <=100
Notice that different roads may have the same source and destination cities.
Output
The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins.
If such path does not exist, only number -1 should be written to the output.
If such path does not exist, only number -1 should be written to the output.
Sample Input
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
Sample Output
11
#include<iostream> #include<cstdio> #include<queue> #include<vector> using namespace std; #pragma warning(disable : 4996) #define MAXN 105 int n,k; typedef struct Node { int end, len, toll; friend bool operator < (Node x, Node y) { if(x.len != y.len) { return x.len > y.len; } return x.toll > y.toll; } }Node; vector<Node> v[MAXN]; priority_queue<Node> Q; int bfs() { int i; Node next, now; while(!Q.empty()) { Q.pop(); } now.end = 1; now.len = 0; now.toll = 0; Q.push(now); while(!Q.empty()) { now = Q.top(); Q.pop(); if(now.end == n) { return now.len; } for(i = 0; i < v[now.end].size(); i++) { if(v[now.end][i].toll + now.toll <= k) { next = v[now.end][i]; next.len += now.len; next.toll += now.toll; Q.push(next); } } } return -1; } int main() { freopen("in.txt", "r", stdin); int i, x, star, end, len, toll; while(scanf("%d%d%d", &k, &n, &x) != EOF) { Node t; for(i = 0; i <= n; i++) { v[i].clear(); } for(i = 1; i <= x; i++) { scanf("%d%d%d%d", &star, &end, &len, &toll); t.end = end; t.len = len; t.toll = toll; v[star].push_back(t); } printf("%d\n", bfs()); } }
DP + SPFA
#include<iostream> #include<queue> #define inf 1<<20 using namespace std; struct node { int end;//一条路的目的地 int len;//一条路的长度 int coin;//一条路得费用 int next; }road[10001]; int k[101];//k[i]表示以I为起点的一条路在road中的位置 bool flag[101];//记录是否在队列中 int d[101][10001]; //d[i][j]表示从1到达i费用为j的路径长度 queue <int> q; int K,N,R,S,D,L,T; void spfa() { int i,j; for(i=2;i<=N;++i) for(j=0;j<=K;++j) d[i][j]=inf; flag[1]=1; q.push(1); while(!q.empty()) { int x=q.front(); q.pop(); flag[x]=0; for(i=k[x];i;i=road[i].next)//所有以x 为起点的路 在road中的位置 { int y=road[i].end;//y 表示 这个路得终点，x是起点 for(j=road[i].coin;j<=K;++j) { if(d[y][j]>d[x][j-road[i].coin]+road[i].len) { d[y][j]=d[x][j-road[i].coin]+road[i].len; if(!flag[y]) { flag[y]=1;//从1 到y得路程发生了改变，则 以y 为起点的路得长度可能也改变 q.push(y); } } } }//for(i) } } int main() { int i; cin>>K>>N>>R; for(i=1;i<=R;++i) { cin>>S>>D>>L>>T; road[i].end=D; road[i].len=L; road[i].coin=T; road[i].next=k[S];//可能存在许多路 有相同的起点和终点 用NEXT把他们联系起来 k[S]=i;//k[]仅仅记录所有具有相同起点的路中最后输入的那一条 } spfa(); int min=inf; for(i=0;i<=K;++i) if(d[N][i]<min)min=d[N][i]; if(min<inf)cout<<min<<endl; else cout<<"-1"<<endl; return 0; }