制限費用のショート例:poj 1724

本題 poj 1724:http://poj.org/problem?id=1724
お金をあげます.kを数えます.nの都市があります.
そして費用はk以内で、1からn都市までの最短距離です.
方法はいろいろあります.優先列+bfs(/dijkstra)を使ってもいいし、spfa+dfs(/dp)を使ってもいいし、vectorで辺の関係を記憶してもいいです.
コード1:優先キュー+bfs

#include 
#include 
#include 
#include 
#include
#include
using namespace std;
#define N 120
int tot;
int first[N];
 int k,n,r;
struct node
{
    int u,l,c;
    friend bool operator b.c;
        else
            return a.l>b.l;
    }
};
struct edge
{
    int v,l,c,next;

}e[N*N];
void addedge(int u,int v,int l,int c,int &tot)
{
    e[tot].v=v;
    e[tot].l=l;
    e[tot].c=c;
    e[tot].next=first[u];
    first[u]=tot++;
}
void init()
{
    memset(first,-1,sizeof(first));
    tot=0;
}
int bfs()
{
    priority_queue q;
    node x;
    x.u=1,x.c=0,x.l=0;
    q.push(x);
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        if(now.u==n)
            return now.l;
        for(int i=first[now.u];i!=-1;i=e[i].next)
        {

       int v=e[i].v,l=e[i].l,c=e[i].c;
            if(now.c+c>k)
                continue;
                node nn;
                nn.u=v;
                nn.c=now.c+c;
                nn.l=now.l+l;
            q.push(nn);
        }
    }
    return -1;
}
int main()
{
    init();
scanf("%d%d%d",&k,&n,&r);
    //cin>>k>>n>>r;
    int u,v,l,c;
    for(int i=0;i>u>>v>>l>>c;
        addedge(u,v,l,c,tot);
    }
    printf("%d
",bfs());
    return 0;
    //cout<

コード2:vectorで辺を保存する

#include 
#include 
#include 
#include 
#include
#include
#include
using namespace std;
#define N 120
int k,n,r;
struct node
{
    int v,l,c;
    friend bool operator b.c;
        else
            return a.l>b.l;
    }
};
vectore[N];
int bfs()
{
    priority_queue q;
    node x;
    x.v=1,x.c=0,x.l=0;
    q.push(x);
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        if(now.v==n)
            return now.l;
        for(int i=0; i

ショートアルゴリズムにはdijkstra、spfa、floyd、Bellman_があります.Ford
4つのアルゴリズムのモデル:http://blog.csdn.net/zhongyanghu27/article/details/8221276