POJ1724 Dij队列优化邻接表

ROADS

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 14737		Accepted: 5341

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.

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 :

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.

Sample Input

Sample Output

题意：起始点为1，终点为n，在不超过费用的情况下找出最短路。

思路：用Dij的话加上队列优化，每次取出路程最短的。找边松弛的时候，只要费用不超过就可以入队，把路程和费用累加存储一起入队即可。取队条件是比较路程，入队条件是不超过费用的情况。取队列的时候如果当前id为n的就可以直接退出了。因为如果终点的边可以进来就表明费用没超过，且路程肯定是最短的。因为这里路程是累加的，如果到达终点路程还比没有到路程的还短，那条路就不用走了，直接break。如果到达路程的没有在取队操作取出来，那就说明还有其他路径有可能会通过其他边更短到达终点

一开始用矩阵存储超时，orz，这里条件说边少点多，我还可以用矩阵。。。。

邻接表的话每个点都有一个模拟链表，当做出边，最后一个置为-1

这里也让我更加理解了Dij算法的思想，每次找出最近的点，通过这个点的出边来松弛到达这个点出边终点的路程，基于贪心思想，一次次通过每条边来松弛，扩展到整个图。

简单模拟下这个算法步骤：

让原点入队，
去队列，弹出，找边
12和13边入队，结束第一次找边
取队内最短路12，弹出，从2开始第二次找边
因为加上24的val值超出范围，所以这一次没有入队
继续取队列最短路，这时候队里面只有13，以3为出边找边....

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define INF  0x3f3f3f3f   //定义一个很大的数
using namespace std;

const int maxn = 10010;

int num,first[maxn];

struct Node {
    int id;
    int len;
    int val;
    }node;

struct Edge {
    int id;//以此点为出边找边
    int len;
    int val;
    int next;
    }e[maxn];

priority_queue<Node> q;

bool operator < (Node a,Node b) {
    return a.len > b.len;
    }

void add(int u,int v,int d,int val) {
    //num边的编号
    e[num].id  = v;
    e[num].val = val;
    e[num].len = d;
    e[num].next = first[u];//邻接表的插入，如果u点开始的有多个边，则当前num边的下一个边为u点起始的上一个边，然后更新first[u]以u开始的边指向当前边的编号
    first[u] = num;        //这就是邻接表不用存储一条边两边端点的原理
    num++;
    }

int main() {
    //freopen("in.txt","r",stdin);
    Node cur;
    int ans = INF;
    int n,m,total;
    while(cin>>total>>n>>m) {
        while(!q.empty())  q.pop();
        memset(first,-1,sizeof(first));
        for(int i = 0; i < m; i++) {
            int t1,t2,c,vv;
            cin>>t1>>t2>>c>>vv;
            add(t1,t2,c,vv);
        }
        //1是起始点
        node.id = 1;
        node.len = 0;
        node.val = 0;
        q.push(node);


        while(!q.empty()) {
            cur = q.top();//筛选路最短的
            q.pop();
            if(cur.id == n){
                    ans = cur.len;
                    break;
            }
            for(int i = first[cur.id]; i != -1; i = e[i].next) {//取当前点的所有出边，通过边松弛，只要小于的都入队
                if(total >= e[i].val+cur.val) {

                    node.id = e[i].id;
                    node.len = cur.len+e[i].len;
                    node.val = e[i].val+cur.val;
                    q.push(node);
                }
            }
        }
    }
        printf(ans<INF?"%d
":"-1
",ans);
        return 0;
    }

超时代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define INF  0x3f3f3f3f   //定义一个很大的数
using namespace std;

const int maxn = 1010;


int mp[maxn][maxn];
int mon[maxn][maxn];


struct Node {
    int num;
    int len;
    int val;
    }node;

priority_queue<Node> q;

bool operator < (Node a,Node b) {
    return a.len > b.len;
    }

int main() {
    //freopen("in.txt","r",stdin);
    Node cur;
    int ans = INF;
    int n,m,total;
    while(cin>>total>>n>>m) {
        while(!q.empty())  q.pop();
        memset(mp,-1,sizeof(mp));
        memset(mon,0,sizeof(mon));
        for(int i = 0; i < m; i++) {
            int t1,t2,c,vv;
            cin>>t1>>t2>>c>>vv;
            mp[t1][t2]=c;
            mon[t1][t2]=vv;
        }
        //1是起始点
        node.num = 1;
        node.len = 0;
        node.val = 0;
        q.push(node);


        while(!q.empty()) {
            cur = q.top();
            q.pop();
            if(cur.num == n){
                    ans = cur.len;
                    break;
            }
            for(int i = 1; i <= n; i++) {
                if(mp[cur.num][i] != -1&& total>=mon[cur.num][i]+cur.val) {

                    node.num = i;//顺序不能倒
                    node.len = cur.len+mp[cur.num][i];
                    node.val = cur.val + mon[cur.num][i];
                    q.push(node);
                }
            }
        }
    }
        printf(ans<INF?"%d
":"-1
",ans);
        return 0;
    }