[洛谷P3946]ことりのおやつ（小鸟的点心）
题目大意：有一张无向图，每条边有一个长度（单位m）每个点有一个高度{h_i}，每秒固定增长g，这个点的高度到{l_i}就不能走了。现在有个人想从s走到t，花不超过g秒时间。要你判断他是否能在g秒内走到，能则输出最短什么时候到（速度1m/s，不用考虑起点和终点的高度）。
解题思路：其实就是最短路问题。只不过在此基础上加上了高度限制而已。
那么我们在更新最短路的时候，也顺便判断高度有没有超限，如果有则不更新。
还有一个坑就是题目描述标亮的地方，我没看到结果95！所以看题一定要仔细！
求最短路Dijkstra或SPFA均可。我用SPFA。
C++ Code：
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
#define N 100005
#define M 1000005
int n,m,s,t,g,q,H[N],L[N],head[N],cnt,dis[N],que[M+5];
bool vis[N];
struct edge{int from,to,dis,nxt;
}e[M];
inline int readint(){char c=getchar();for(;!isdigit(c);c=getchar());int d=0;for(;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^'0');return d;
}
int main(){cnt=0;n=readint(),m=readint(),s=readint(),t=readint(),g=readint(),q=readint();for(int i=1;i<=n;++i)H[i]=readint(),L[i]=readint();while(m--){int u=readint(),v=readint(),t=readint();e[++cnt]=(edge){u,v,t,head[u]};head[u]=cnt;e[++cnt]=(edge){v,u,t,head[v]};head[v]=cnt;}memset(dis,0x3f,sizeof dis);memset(vis,0,sizeof vis);dis[que[1]=s]=0;int l=0,r=1;while(l!=r){int now=que[l=l%M+1];vis[now]=false;for(int i=head[now];i;i=e[i].nxt){int v=e[i].to,d=dis[now]+e[i].dis;if(dis[v]>d&&(v==t||(long long)q*d+H[v]<=L[v])){dis[v]=d;if(!vis[v]){vis[v]=true;que[r=r%M+1]=v;}}}}if(dis[t]<=g)printf("%d\n",dis[t]);elseputs("wtnap wa kotori no oyatsu desu!");return 0;
}
转载于:.html
[洛谷P3946]ことりのおやつ（小鸟的点心）
题目大意：有一张无向图，每条边有一个长度（单位m）每个点有一个高度{h_i}，每秒固定增长g，这个点的高度到{l_i}就不能走了。现在有个人想从s走到t，花不超过g秒时间。要你判断他是否能在g秒内走到，能则输出最短什么时候到（速度1m/s，不用考虑起点和终点的高度）。
解题思路：其实就是最短路问题。只不过在此基础上加上了高度限制而已。
那么我们在更新最短路的时候，也顺便判断高度有没有超限，如果有则不更新。
还有一个坑就是题目描述标亮的地方，我没看到结果95！所以看题一定要仔细！
求最短路Dijkstra或SPFA均可。我用SPFA。
C++ Code：
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
#define N 100005
#define M 1000005
int n,m,s,t,g,q,H[N],L[N],head[N],cnt,dis[N],que[M+5];
bool vis[N];
struct edge{int from,to,dis,nxt;
}e[M];
inline int readint(){char c=getchar();for(;!isdigit(c);c=getchar());int d=0;for(;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^'0');return d;
}
int main(){cnt=0;n=readint(),m=readint(),s=readint(),t=readint(),g=readint(),q=readint();for(int i=1;i<=n;++i)H[i]=readint(),L[i]=readint();while(m--){int u=readint(),v=readint(),t=readint();e[++cnt]=(edge){u,v,t,head[u]};head[u]=cnt;e[++cnt]=(edge){v,u,t,head[v]};head[v]=cnt;}memset(dis,0x3f,sizeof dis);memset(vis,0,sizeof vis);dis[que[1]=s]=0;int l=0,r=1;while(l!=r){int now=que[l=l%M+1];vis[now]=false;for(int i=head[now];i;i=e[i].nxt){int v=e[i].to,d=dis[now]+e[i].dis;if(dis[v]>d&&(v==t||(long long)q*d+H[v]<=L[v])){dis[v]=d;if(!vis[v]){vis[v]=true;que[r=r%M+1]=v;}}}}if(dis[t]<=g)printf("%d\n",dis[t]);elseputs("wtnap wa kotori no oyatsu desu!");return 0;
}
转载于:.html