Trips and Universities题解

Trips and Universities

前置知识

图的基础知识（只看前一部分就行）

分析题目

有向图，边有边权。不考虑学院的话其实就是一道普通的最短路问题。

那么，现在考虑进学院。我们注意到，题目中学院的条件很奇怪：

必须上一次在 $p_i$ 城市的学院学习才能在该学院学习。每个学院只能学习一次。

其实，对于处理这种较为特殊的、看起来要使用最短路解决的问题，我们有一种建图技巧：分层图。

简单来说，就是将问题划分为若干个阶段（通常很少），对于每一个阶段，我们都建一层完整的图，层与层之间根据题目要求用合适的边连接。

比方说这道题，我们将每修完一所学院划为一个阶段。学院 \(i\) 相当于在当前层于下一层的对应节点之间连接了一条边权为 \(c_i - g_i\) 的边。在这个图上跑最短路即可。

细节实现参见代码。

代码

#define INF 0x3f3f3f3f3f3f3f3f

#include 
#include 
#include 
#include 
#include 

using namespace std;

inline int read(){
	int t = 0,flag = 1;
	register char c = getchar();
	while (c < 48 || c > 57) {if (c == '-') flag = -1;c = getchar();}
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
	return flag * t;
}//快读，可忽略 

inline long long min(long long a,long long b) {return a < b ? a : b;}

struct edge{
	int u,v,w,next;
}e[40601];

queue  q;

int n,m,k,u,v,w,f,c,g,p,tot,etot,head[20001],from[60],to[50];//(from[i],to[i])代表i学院在图中的边从第from[i]层连到to[i]层 
long long ans[200001],dis[20001];
bool inque[20001];

void addedge(int u,int v,int w){
	e[++etot].u = u,e[etot].v = v,e[etot].w = w,e[etot].next = head[u],head[u] = etot;
}//建图 

void SPFA(){
	memset(inque,0,sizeof(inque)),memset(dis,63,sizeof(dis)),q.push(1),inque[1] = 1,dis[1] = 0;
	while (!q.empty()){
		int now = q.front();
		q.pop(),inque[now] = 0;
		for (int i = head[now];i;i = e[i].next){
			if (dis[e[i].v] > dis[now] + e[i].w){
				dis[e[i].v] = dis[now] + e[i].w;
				if (!inque[e[i].v]) q.push(e[i].v),inque[e[i].v] = 1;
			}
		}
	}
}//最短路：SPFA。写Bellman-ford应该也行

int main(){
	from[0] = -1,n = read(),m = read(),k = read();//将from[0]设为-1是为了后面方便 
	for (int i = 1;i <= m;i++){
		u = read(),v = read(),w = read();
		for (int j = 0;j <= k;j++){
			addedge(u + n * j,v + n * j,w);//先建好每一层图，层与层之间先不连通，可以举例理解 
		}
	}
	for (int i = 1;i <= k;i++){
		f = read(),c = read(),g = read(),p = read();
		from[f] = to[p],to[f] = ++tot;//更新层数 
		addedge(f + n * from[f],f + n * to[f],c - g);//连边，可以自己举几个例子理解 
	}	
	SPFA();
	for (int i = 1;i <= n;i++){
		ans[i] = INF;//因为要取最小值，先将答案初始化为无穷 
		for (int j = 0;j <= k;j++) ans[i] = min(ans[i],dis[i + n * j]);//由于到哪一层停止都可以，所以要每一层取最小值 
		if (ans[i] == INF) puts("ERROR");//ans[i] == INF 说明ans[i]没有更新，即无法到达i 
		else printf("%lld\n",ans[i]);
	}
	return 0;
}