HDU5168 – Legal path(最短路dijkstra变形 OR 单调队列DP)

题目链接 HDU5168

【题意】一个有向图，给定起点终点，每条边上有权值。
一条合法的路径定义为相邻边的权值之差不小于K的路径，即路径上每条边的权值至少要比上一条边的权值大K ，如果上一条边存在。合法路径的长度定义为路径上的边权值总和。
求从起点到终点的合法路径的最短长度。

【分析】用dijkstra竟然也能过，多加一个la[]维护每个点的上一条边的花费，需要注意的是当c当前边cost<la[v]时也要更新(即需要让每个la[]劲量保持最小以得到后面更多的可能)，这样变形的dijkstra中dis[]不一定和队列中的dis相等，还有一点：不是一个点访问过就不能访问，而是当新的cost<la[v]时也要入队(就是上面说过的更新)。具体看代码吧。

而标程应该是用N个单调队列对每个点维护上一条边的权值和到当前点的最短距离，具体看代码。

【AC CODE(dijkstra)】967ms
数据有点弱，vis标记放在入队的时候都对了，导致跑了592ms侥幸排第一了，其实是错的，下面的才是对的，需要把更新放在开始(即出队下方)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int MAXN = 100000+10, MAXM = 200000+10;
const LL INF = 4557430888798830399;
struct Edge{
    int next,to,cost;
    Edge(int a = 0, int b = 0, int c = 0){
        next = a, to = b, cost = c;
    }
}edge[MAXM];
struct NODE{
    LL dis, la;//这里的dis不一定是dis[u]
    int u;
    NODE(LL a = 0, LL b = 0, int c = 0){ dis = a, la = b, u = c;}
    bool operator <(const NODE& a) const {return dis > a.dis;}
};
int tol,head[MAXN], k;
LL dis[MAXN], la[MAXN];
bool vis[MAXN];

void add_edge(int u, int v, int cost)
{
    edge[tol] = Edge(head[u],v,cost);
    head[u] = tol++;
}
void dijkstra(int st)
{
	priority_queue<NODE> q;
	clc(dis, 0x3f);
	clc(vis, 0);
	clc(la, 0x3f);
	dis[st] = 0;
	la[st] = -INF;
	q.push(NODE(dis[st], la[st], st));
	while (!q.empty())
	{
		NODE now = q.top(); q.pop();
		int u = now.u;
		if(dis[u] > now.dis) dis[u] = now.dis;
		if(vis[u] && la[u] <= now.la) continue;
		vis[u] = true;
		la[u] = now.la;
		for (int i = head[u]; ~i; i = edge[i].next)
		{
			int v = edge[i].to;
			LL cost = edge[i].cost;
			/*下面不能用dis[u]替换now.dis 两者不一定相等*/
			if (cost - la[u] >= k && (dis[v] > now.dis + cost || cost < la[v]))
				q.push(NODE(now.dis + cost, cost, v));
		}
	}
}
int main()
{
#ifdef SHY
    freopen("e:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d%*c", &t);
    while(t--)
    {
        int n,m;
        scanf("%d %d %d%*c", &n, &m, &k);
        int a,b,c;
        tol = 0;
        clc(head,-1);
        rep(i,0,m)
        {
            scanf("%d %d %d%*c", &a, &b, &c);
            add_edge(a,b,c);
        }
        dijkstra(1);
        if(INF == dis[n]) puts("-1");
        else printf("%I64d\n", dis[n]);
    }
    return 0;
}
/*
1
6 7 2
1 2 2
2 3 4
3 4 6
1 5 3
5 4 8
4 6 8
4 6 10
=======
20
*/

【AC CODE(单调队列DP)】1425ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int MAXN = 100000+10, MAXM = 200000+10;
const LL INF = 4557430888798830399;
struct NODE{
	LL c;//c是上一条边的花费
	LL val;// val是i点的最短距离
	NODE(LL a, LL b){
		c = a, val = b;
	}
};
struct Edge{
	int u,v,cost;
	bool operator<(const Edge& t)const{
		return cost < t.cost;
	}
}edge[MAXM];
deque<NODE> q[MAXN];
LL dp[MAXN];

int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d%*c", &t);
	while(t--)
	{
		int n,m,k;
		scanf("%d %d %d%*c", &n, &m, &k);
		repe(i,1,n) q[i].clear();
		rep(i,0,m) scanf("%d %d %d%*c", &edge[i].u, &edge[i].v, &edge[i].cost);
		sort(edge,edge+m);
		clc(dp,0x3f);
		repe(i,1,n) q[i].push_back(NODE(-INF,INF));
		dp[1] = 0;
		rep(i,0,m)
		{
			int u = edge[i].u, v = edge[i].v, cost = edge[i].cost;
			NODE nxt = NODE(cost,INF);
			if(1 == u)
				nxt.val = cost;
			else
			{
				//找到上一条边合法的最小值,先删除队列中不合法的
				while(q[u].size() > 1 && cost-k >= q[u][1].c)
					q[u].pop_front();
				nxt.val = q[u][0].val+cost;
			}
			if(nxt.val < q[v][q[v].size()-1].val)
			{
				while(q[v].size() > 1 && nxt.val >= q[v][q[v].size()-1].val) q[v].pop_back();
				q[v].push_back(nxt);
			}
			dp[v] = min(dp[v], nxt.val);
		}
		if(INF == dp[n]) puts("-1");
		else printf("%I64d\n", dp[n]);
	}
	return 0;
}