POJ 3159 Candies(最短路解差分约束)

Description

堆(优先队列)优化的Dijkstra

用栈(而非队列)实现spfa

Analyze

题目是求从1到n的最短路（差分约束）

关键在于算法的优化

①堆优化的Dijkstra：

我之前的Dijkstra都是手动去模拟那个优化过程的，可能因为模拟地不准确而效果不好？易TLE

②栈实现的spfa：

spfa是对Bellman-Ford的优化，Bellman-Ford是在暴力求解最短路。

假设：图只是一棵树，1起点，n终点，从终点向起点添边，则复杂度达到最大n*m,n-1次对m条边的松弛，每次对m条边松弛只有一次是有用的！

而spfa是以松弛过的点为基去松弛，保证了大部分松弛都是有效的，至少是可能的

而spfa的实现，按理说用队列还是栈没区别，但事实是：用栈比用队列快？？？而且前提是没有负环？？？

Code

#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 30005;
const int INF = 0x3f3f3f3f;

struct edge
{
    int to, w, pre;
} a[N * 5];

typedef pair<int, int> P;

int n, m;
bool vis[N];
int head[N], cnt, dis[N];

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
        dis[i] = INF, vis[i] = 0, head[i] = -1;
}

void add(int from, int to, int w)
{
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt++;
}

void dijkstra(int start)
{
    priority_queue<P, vector<P>, greater<P> > q;
    dis[start] = 0;
    q.push( P(0, start) );
    while(!q.empty())
    {
        P now = q.top();
        q.pop();

        int dist = now.first;
        int idx = now.second;
        if(dis[idx] < dist)///vis[idx] == 1
            continue;
        for(int i = head[idx]; ~i; i = a[i].pre)
        {
            int v = a[i].to;
            if(dis[v] > dis[idx] + a[i].w)
            {
                dis[v] = dis[idx] + a[i].w;
                q.push(P(dis[v], v));
            }
        }
    }
}

void spfa(int start)
{
    stack<int> st;
    dis[start] = 0;
    vis[start] = 1;
    st.push(start);
    while(!st.empty())
    {
        int now = st.top();
        st.pop();
        vis[now] = 0;
        for(int i = head[now]; ~i; i = a[i].pre)
        {
            int v = a[i].to;
            if(dis[v] > dis[now] + a[i].w)
            {
                dis[v] = dis[now] + a[i].w;
                if(!vis[v])
                {
                    st.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        init();
        int u, v, w;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
        }
//        dijkstra(1);
        spfa(1);
        cout << dis[n] << '\n';
    }
    return 0;
}

另外补充一句：普通的队列与栈，都可以用数组模拟