先跑一遍 n 为起点最短路, 再新开一个点, 向有干草垛的点连一根边权为 d[u]-w 的有向边 (很重要.. 我当时连的无向边, 然后我死了.), 相当于用价值抵消一部分边权,
然后以这个新的点为起点跑最短路就好了...
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<queue>
- #define pc(x) putchar(x)
- #define R register int
- using namespace std;
- const int N=50010,M=100010;
- inline int g() {
- R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
- do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
- }
- int n,m,k,cnt;
- int vr[M<<1],nxt[M<<1],w[M<<1],fir[N],d[N],f[N];
- bool vis[N];
- priority_queue<pair<int,int>> q;
- inline void add(int u,int v,int ww) {vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;}
- inline void dijk() {
- memset(d,0x3f,sizeof(int)*(n+2)); d[n]=0,q.push(make_pair(0,n));
- while(q.size()) {
- R u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=true;
- for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
- if(d[v]>d[u]+w[i]) d[v]=d[u]+w[i],q.push(make_pair(-d[v],v));
- }
- }
- }
- inline void dijk2() {
- memset(f,0x3f,sizeof(int)*(n+3)); f[n+1]=0,q.push(make_pair(0,n+1));
- memset(vis,false,sizeof(bool)*(n+3)); while(q.size()) {
- R u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=true;
- for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
- if(f[v]>f[u]+w[i]) f[v]=f[u]+w[i],q.push(make_pair(-f[v],v));
- }
- }
- }
- signed main() {
- n=g(),m=g(),k=g(); for(R i=1,u,v,w;i<=m;++i) u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w);
- dijk(); for(R i=1,u,w;i<=k;++i) u=g(),w=g(),add(n+1,u,d[u]-w); dijk2();
- for(R i=1;i<n;++i) f[i]<=d[i]&&d[i]!=0x3f3f3f3f?(pc('1'),pc('\n')):(pc('0'),pc('\n'));
- }
- 2019.04.24
来源: http://www.bubuko.com/infodetail-3034981.html