POJ 1724 ROADS

链接：http://poj.org/problem?id=1724

题意：在价格和长度两个条件限制下求出最短路，即求出价格不超过K的最短路。

思路：用SPFA，vv数组用二维，其余就是普通的最短路问题。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 105
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int point [maxn];
int dis[maxn][10005];
int vv[maxn][10005];
struct Edge
{
    int v,w,t;
    int next;
}edge[maxn*maxn];
struct Node
{
    int pos,v;
}re,ne;
int top=0;
int init()
{
    top=0;
    memset(point,-1,sizeof(point));
    memset(vv,0,sizeof(vv));
    memset(dis,-1,sizeof(dis));
    return 0;
}
int add_edge(int v1,int v2,int w,int t)
{
    edge[top].v=v2;
    edge[top].w=w;
    edge[top].t=t;
    edge[top].next=point[v1];
    point[v1]=top++;
    return 0;
}
int main()
{
    int lim,cc,rr;
    init();
    scanf("%d%d%d",&lim,&cc,&rr);
    for(int i=0; i<rr; i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add_edge(a,b,c,d);
    }
    queue<Node>qq;
    re.pos=1;
    re.v=0;
    qq.push(re);
    vv[re.pos][re.v]=1;
    dis[re.pos][re.v]=0;
    while(!qq.empty())
    {
        re=qq.front();
        qq.pop();
        vv[re.pos][re.v]=0;
        for(int i=point[re.pos];i!=-1;i=edge[i].next)
        {
            ne.pos=edge[i].v;
            ne.v=re.v+edge[i].t;
            if(ne.v>lim)
            continue;
            if(dis[ne.pos][ne.v]==-1||dis[re.pos][re.v]+edge[i].w<dis[ne.pos][ne.v])
            {
                dis[ne.pos][ne.v]=dis[re.pos][re.v]+edge[i].w;
                if(!vv[ne.pos][ne.v])
                {
                    vv[ne.pos][ne.v]=1;
                    qq.push(ne);
                }
            }
        }
    }
    int ans=-1;
    for(int i=1;i<=lim;i++)
    {
        if(dis[cc][i]!=-1&&ans==-1)
        ans=dis[cc][i];
        else if(dis[cc][i]!=-1&&dis[cc][i]<ans)
        ans=dis[cc][i];
    }
    printf("%d\n",ans);
}

POJ 1724 ROADS

原文：http://blog.csdn.net/ooooooooe/article/details/19249443