NWERC2018 Date Pickup
题目大意
给出一张图，R在1，J在n，J会在[a,b]时发出信号，R会在接到信号后直达n点，在此之前，R需要计划一条路线，在家等一段时间后出发，问J需要等候时间的最大值最小是多少。
题解
求出每个点到起点和终点的距离，二分答案w，将到起点+终点距离<=a+w的点标记为好的，如果一条边(u,v)中u是好的，且这条边长度+v到终点距离<=w，将v和这条边标记成好的，然后考虑所有好的边，如果这个图有环则合法，否则如果在图中停留时间长度>=b合法，否则不合法。
求图中停留时间长度：latest[i]表示在i点时的最长停留时间长度，初始时latest[i]=a+w-到终点距离，然后在新图中dp即可，latest[v]=max(latest[v],latest[u]+len)。
处理在家停留情况，需要在原图中加一条从1到1长度为0的边。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #define ll long long #define pii pair<ll,int> using namespace std; priority_queue<pii,vector<pii>,greater<pii> > q; queue<int> q1; int read() { char ch=getchar();int f=0,x=1; while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();} while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();} return f*x; } int n,m;ll a,b;bool ok[100005]; ll dis1[100005],dis2[100005],d[100005],latest[100005]; int du[100005]; struct graph { struct node { int from; int to; int next; int w; int ok; }edge[200005]; int tot,head[100005]; void init() { memset(head,-1,sizeof(head)); tot=0; } void add(int u,int v,int w) { edge[tot].from=u; edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } void dijkstra(ll *dis,int x) { q.push(pii(0,x));dis[x]=0; while(!q.empty()) { pii temp=q.top();q.pop(); x=temp.second; if(dis[x]!=temp.first) continue; for(int i=head[x];i!=-1;i=edge[i].next) { if(dis[edge[i].to]>dis[x]+edge[i].w) { dis[edge[i].to]=dis[x]+edge[i].w; q.push(pii(dis[edge[i].to],edge[i].to)); } } } } void check(ll num) { for(int i=0;i<tot;i++) edge[i].ok=0; while(!q1.empty()) { int x=q1.front();q1.pop(); for(int i=head[x];i!=-1;i=edge[i].next) { if(dis2[edge[i].to]+edge[i].w<=num) { edge[i].ok=1; du[edge[i].to]++; if(!ok[edge[i].to]) { q1.push(edge[i].to); ok[edge[i].to]=1; latest[edge[i].to]=a+num-dis2[edge[i].to]; }//*/ } } } } void solve() { for(int i=1;i<=n;i++) d[i]=-10000000000000LL; for(int i=1;i<=n;i++) { if(ok[i]&&!du[i]) q1.push(i),d[i]=0; } while(!q1.empty()) { int x=q1.front();q1.pop(); for(int i=head[x];i!=-1;i=edge[i].next) { if(!ok[edge[i].to]||!edge[i].ok) continue; du[edge[i].to]--; latest[edge[i].to]=max(latest[edge[i].to],latest[x]+edge[i].w); if(!du[edge[i].to]) q1.push(edge[i].to); } } } }g1,g2; bool check(ll x) { memset(ok,0,sizeof(ok)); memset(du,0,sizeof(du)); for(int i=1;i<=n;i++) latest[i]=-100000000000000LL; for(int i=1;i<=n;i++) { if(dis1[i]+dis2[i]<=a+x) { ok[i]=1; q1.push(i); latest[i]=a+x-dis2[i]; } } if(!ok[n]) return 0; g1.check(x); g1.solve(); for(int i=1;i<=n;i++) { if(du[i]) return 1; } if(latest[n]>=b) return 1; return 0; } int main() { cin>>a>>b; n=read();m=read(); g1.init();g2.init(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); g1.add(u,v,w); g2.add(v,u,w); } g1.add(1,1,0); g2.add(1,1,0); for(int i=1;i<=n;i++) { dis1[i]=dis2[i]=100000000000000LL; } g1.dijkstra(dis1,1); g2.dijkstra(dis2,n); ll l=0,r=1000000000000LL,ans=r; while(l<=r) { ll mid=l+r>>1LL; if(check(mid)) { ans=mid; r=mid-1; } else l=mid+1; }//*/ cout<<ans; } |