https://www.luogu.org/problemnew/show/P5122

题意：n个点，含有k个干草堆，问前n-1个点到第n个点的【经过任一干草堆的最短路】减去【不加限制的最短路】是否不超过那个干草堆的美味值。

思路：

①搞Dijkstra的变形，设d[i][0]为i到n的最短路，d[i][1]为i到n的经过干草堆的最短路减去那个干草堆的美味值的大小。松弛操作跟着变形。最后判断每个点是否d[i][1]<=d[i][0]

②加一个虚拟结点n+1，向k个干草堆连边，权值为每个干草堆到n的最短路减去美味值。跑两次Dijkstra即可。最后判断每个点是否d[i]<=d2[i]

无向图，直接从终点n往回跑就行了。

Q：为什么要把美味值加到边权里，不能最后判断每个点是否满足【经过干草堆的最短路】-美味值<=【不加限制的最短路】呢？

A：对于任一点i，如果最后判断，不知道【经过干草堆的最短路】经过的是哪个，也就不知道减的是哪个干草堆的美味值，而且，在Dijkstra处理中，对于这k个干草堆是不能一视同仁的，要综合考虑i经过每个干草堆到n的距离大小以及每个干草堆的美味值。故应该把美味值作为经过那个干草堆的路径的固有属性。

①：

#include<bits/stdc++.h>
using namespace std;
#define maxn 50000+1000
#define INF 0x3f3f3f3f

struct Edge{
	int from,to,dist;
};
struct HeapNode{
	int u,flag,d;
	bool operator < (const HeapNode& x)const{
		return d>x.d;
	}
};
int n,m,k,y[maxn];
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn][2];
int d[maxn][2];

void init()
{
	edges.clear();
	for(int i=1;i<=n;i++)G[i].clear();
}

void AddEdge(int f,int t,int d)
{
	edges.push_back((Edge){f,t,d});
	G[f].push_back(edges.size()-1);
}

void dijkstra(int s)
{
	priority_queue<HeapNode> Q;
	for(int i=1;i<=n;i++)d[i][0]=d[i][1]=INF;
	d[s][0]=0;
	memset(vis,0,sizeof(vis));
	Q.push((HeapNode){s,0,0});
	while(!Q.empty())
	{
		HeapNode x=Q.top();
		Q.pop();
		int u=x.u,flag=x.flag;
		if(vis[u][flag])continue;
		vis[u][flag]=1;
		for(int i=0;i<G[u].size();i++)
		{
			Edge& e=edges[G[u][i]];
			int v=e.to;
			if(!flag)
			{
				if(d[v][0]>d[u][0]+e.dist)
				{
					d[v][0]=d[u][0]+e.dist;
					Q.push((HeapNode){v,0,d[v][0]});
				}
				if(y[v]&&d[v][1]>d[u][0]+e.dist-y[v])
				{
					d[v][1]=d[u][0]+e.dist-y[v];
					Q.push((HeapNode){v,1,d[v][1]});
				}
			}
			else
			{
				if(d[v][1]>d[u][1]+e.dist)
				{
					d[v][1]=d[u][1]+e.dist;
					Q.push((HeapNode){v,1,d[v][1]});
				}
			}
		}
	}
}

int main()
{
//	freopen("input.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	int a,b,c;
	while(m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		AddEdge(a,b,c);
		AddEdge(b,a,c);
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&a,&b);
		y[a]=b;
	}
	dijkstra(n);
	
	for(int i=1;i<n;i++)
		if(d[i][1]<=d[i][0])puts("1"); else puts("0");
	return 0;
}

②：

#include<bits/stdc++.h>
using namespace std;
#define maxn 50000+1000
#define INF 0x3f3f3f3f

struct Edge{
	int from,to,dist;
};
struct HeapNode{
	int u,d;
	bool operator < (const HeapNode& x)const{
		return d>x.d;
	}
};
int n,m,k,y[maxn];
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];
int d[maxn],d2[maxn];

void init()
{
	edges.clear();
	for(int i=1;i<=n;i++)G[i].clear();
}

void AddEdge(int f,int t,int d)
{
	edges.push_back((Edge){f,t,d});
	G[f].push_back(edges.size()-1);
}

void dijkstra(int s,int *d)
{
	priority_queue<HeapNode> Q;
	for(int i=1;i<=n;i++)d[i]=d[i]=INF;
	d[s]=0;
	memset(vis,0,sizeof(vis));
	Q.push((HeapNode){s,0});
	while(!Q.empty())
	{
		HeapNode x=Q.top();
		Q.pop();
		int u=x.u;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++)
		{
			Edge& e=edges[G[u][i]];
			int v=e.to;		
			if(d[v]>d[u]+e.dist)
			{
				d[v]=d[u]+e.dist;
				Q.push((HeapNode){v,d[v]});
			}			
		}
	}
}

int main()
{
//	freopen("input.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	int a,b,c;
	while(m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		AddEdge(a,b,c);
		AddEdge(b,a,c);
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&a,&b);
		y[a]=b;
	}
	dijkstra(n,d);
	for(int i=1;i<=n;i++)if(y[i])
	{
		AddEdge(n+1,i,d[i]-y[i]);
	}
	dijkstra(n+1,d2);
	for(int i=1;i<n;i++)
		if(d2[i]<=d[i])puts("1"); else puts("0");
	return 0;
}