poj 1724 ROADS 加限制的最短路

本文主要是介绍poj 1724 ROADS 加限制的最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//SPFA+二维数组记录状态

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=10005;
int n, m, d[105][maxn], pre[maxn], inqueue[maxn], cnt, money, count[maxn];
struct node{
     int v, w, l, next;
}edge[maxn];
void add_edge(int s, int e, int w, int len){
    edge[cnt].v=e;
    edge[cnt].w=w;
    edge[cnt].l=len;
    edge[cnt].next=pre[s];
    pre[s]=cnt;
    cnt++;
}

void init(){
    int i, x, y, c, len;
    cnt=1;
    scanf("%d%d%d", &money, &n, &m);
    for(i=1; i<=n; i++){
        pre[i]=-1;
        count[i]=0;
    }
    for(i=0; i<m; i++){
        scanf("%d%d%d%d", &x, &y, &len, &c);
        add_edge(x, y, c, len);
    }
}

bool spfa(int st){
    int i, j, head, s;
    memset(d, 0 , sizeof(d));
    for(i=2; i<=n; i++){
        inqueue[i]=0;
        for(j=0; j<=money; j++)
        d[i][j]=INF;
    }
    queue<int > q;
    inqueue[st]=1;
    q.push(st);
    while(!q.empty()){
        head=q.front();
        q.pop();
        inqueue[head]=0;
        s=pre[head];
        while(s!=-1){
            for(i=edge[s].w; i<=money; i++){
            if(d[edge[s].v][i]>d[head][i-edge[s].w]+edge[s].l){
                d[edge[s].v][i]=d[head][i-edge[s].w]+edge[s].l;
                if(!inqueue[edge[s].v]){
                    count[edge[s].v]++;
                    if(count[edge[s].v]>=n)return false;
                     inqueue[edge[s].v]=1;
                     q.push(edge[s].v);
                }
            }
            }
            s=edge[s].next;
        }
    }
    return true;
}

int main(){
    //freopen("1.txt", "r", stdin);
    int i, T;
    int ans;
    init();
    if(spfa(1)){
        ans=INF;
        for(i=0; i<=money; i++){
            if(d[n][i]<ans)
            ans=d[n][i];
        }
    }
    else ans=-1;
    printf("%d\n", ans);
    return 0;
}