思路：最短路+dp
1、先跑一遍最短路，计算出没有干草垛最少要多少时间
2、dp求出有干草垛至少需要多少时间，由于dp有后效性，所以用SPFA辅助转移，dp方程和求最短路一模一样，只是先将有干草垛的拉入队列转移，仅此而已。
代码非常简单，可以说是两遍一模一样的SPFA：
#include<bits/stdc++.h>
#define maxn 1000001
#define INF 1926081700
using namespace std;
long long cnt,cost[maxn],from[maxn],to[maxn],Next[maxn],head[maxn];
long long dis[maxn],dp[maxn],point[maxn],vis[maxn];
long long n,m,k;
queue<long long>q;
void add(long long x,long long y,long long z){
cnt++;cost[cnt]=z;
from[cnt]=x;to[cnt]=y;
Next[cnt]=head[x];head[x]=cnt;
}
void SPFA(long long S){ //SPFA板子
for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0;
q.push(S);vis[S]=1;dis[S]=0;
while(!q.empty()){
long long u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i!=-1;i=Next[i]){
long long v=to[i];
if(dis[v]>dis[u]+cost[i]){
dis[v]=dis[u]+cost[i];
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
}
void BFS(int S){ //dp
for(int i=1;i<=n;i++)dp[i]=INF,vis[i]=0;
//**************************dp唯一与SPFA不同的地方**************************
for(int i=1;i<=n;i++)
if(point[i]>0){
dp[i]=dis[i]-point[i];
q.push(i);vis[i]=1;
}
//**************************dp唯一与SPFA不同的地方**************************
while(!q.empty()){
long long u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i!=-1;i=Next[i]){
long long v=to[i];
if(dp[v]>dp[u]+cost[i]){
dp[v]=dp[u]+cost[i];
if(vis[v]==0){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)point[i]=0;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;i++){
long long x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);add(y,x,z); //建边
}
SPFA(n);
for(int i=1;i<=k;i++){
long long x,y;
scanf("%lld%lld",&x,&y);
point[x]=max(point[x],y); //加入干草垛
}
BFS(n);
for(int i=1;i<=n-1;i++){
if(dp[i]<=dis[i]) //判断，输出
printf("1
");
else
printf("0
");
}
return 0;
}