前置知识
图的基础知识（只看前一部分就行）
分析题目
有向图，边有边权。不考虑学院的话其实就是一道普通的最短路问题。
那么，现在考虑进学院。我们注意到，题目中学院的条件很奇怪：
必须上一次在 $p_i$ 城市的学院学习才能在该学院学习。每个学院只能学习一次。
其实，对于处理这种较为特殊的、看起来要使用最短路解决的问题，我们有一种建图技巧：分层图。
简单来说，就是将问题划分为若干个阶段（通常很少），对于每一个阶段，我们都建一层完整的图，层与层之间根据题目要求用合适的边连接。
比方说这道题，我们将每修完一所学院划为一个阶段。学院 \(i\) 相当于在当前层于下一层的对应节点之间连接了一条边权为 \(c_i - g_i\) 的边。在这个图上跑最短路即可。
细节实现参见代码。
代码
#define INF 0x3f3f3f3f3f3f3f3f
#include <queue>
#include <cstdio>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
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 <int> 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;
}