中文旅游网站html模板,杭州网络公司建网站,网站架构搭建,海南省住房公积金管理局网上办事大厅【题目背景】 开学了#xff0c;小奇在回地球的路上#xff0c;遇到了一个棘手的问题。 【问题描述】 简单来说#xff0c;它要从标号为 1 的星球到标号为 n 的星球#xff0c;某一些星球之间有航线。 由于超时空隧道的存在#xff0c;从一个星球到另一个星球时间可能会倒…【题目背景】 开学了小奇在回地球的路上遇到了一个棘手的问题。 【问题描述】 简单来说它要从标号为 1 的星球到标号为 n 的星球某一些星球之间有航线。 由于超时空隧道的存在从一个星球到另一个星球时间可能会倒流而且从星 球 a 到 b 耗费的时间和星球 b 到 a 耗费的时间不一定相同。宇宙法规定“禁止在出发时间前到达目的地”。每艘飞船上都有速度调节装置可以调节飞行的时间。其功能可以使得整次航程中所有两星球间的飞行时间增加或减少相同的整数值。你的任务是帮助它调整速度调节器找出一条最短时间到达目的地的路径。 【输入格式】 输入文件包含多组数据第 1 个数为 T表示数据组数。对于每组数据输入第 1 行为两个正整数 nm为星球的个数和星球间的路线数。接下来 m 行每行三个整数 ij 和 t表示由星球 i 到星球 j 飞行的时间为 t。由 i 到 j 最多只会有一条飞行线路。 【输出格式】 输出文件共 T 行每组数据输出一行。 如果可以通过调节速度调节器完成任务则输出一个非负整数表示由星球1到星球 n 的最短时间。注意最短时间要大于或者等于 0。如果不能由星球 1 到达星球 n则输出-1。 【样例输入】 1 4 5 1 2 1 1 3 1 2 3 -3 3 1 1 3 4 1 【样例输出】 2 【样例解释】 把速度控制器的值设为 1,相当于每个时间值加 1,得到的最短路径为 1→2→3→4。所需时间为 2(-2)22。 【数据范围】 12 号测试点保证所有星球出度不超过1 34 号测试点n10 56 号测试点-100t100 对于 100%的数据 T10n100mn*(n-1)-100000t100000 数据随机和构造结合生成 【解析】 将此题简化后可得如下模型给定一张有向图有负边权,可以使每一条边加上或减去一个值t使从1到n的最短路径最小且非负。 经过分析可以知道若给每一条边加上一个值t0后1到n的最短路为负那么对于任意tt0都有最短路径仍为负。由此可以想到二分答案。t的值域为-100000到100000那么二分的左右边界就定好了。然后每次都用SPFA检验最短路径是否大于等于0然后......死循环了。 为什么呢假设有t10那么图中就有几率出现负权环那么就没有最短路。所以要在SPFA中加入判断负权环的内容。但即使这样仍会超时。那么我们继续思考怎么优化。显然如果一个点与1或n不连通那么它对答案是没有贡献的。我们先从1出发遍历整张图把无法到达的点删去。然后再从1能够到达的点出发如果该点不能到达n也从集合中删去。在“砍图”之后虽然时间已经优化了但仍然不够。题目中有一句话是这么说的 数据随机和构造结合生成 那是不是会卡SPFA呢所以一个神奇的操作就出来了深度优先搜索版SPFA。用DFS-SPFA去判断负权环即可。 【代码】 #include iostream
#include cstdio
#include cstring
#include queue
#define N 102
#define M 200002
using namespace stdint head[N],ver[M],nxt[M],edge[M],c;
int t,n,m,i,cnt[N],dis[N];
bool e[N],vis[N],in[N];
queueint q;
int read()
{char cgetchar();int w0,f1;while(c0||c9){if(c-) f-1;cgetchar();}while(c9c0){ww*10c-0;cgetchar();}return w*f;
}
void insert(int x,int y,int z)
{c;ver[c]y;edge[c]z;nxt[c]head[x];head[x]c;
}
bool dfs_SPFA(int x,int s)
{vis[x]1;for(int ihead[x];i;inxt[i]){int yver[i];if(dis[y]dis[x]edge[i]se[y]){if(vis[y]) return 1;dis[y]dis[x]edge[i]s;if(dfs_SPFA(y,s)) return 1;}}vis[x]0;return 0;
}
void SPFA(int s)
{memset(dis,0x3f,sizeof(dis));memset(in,0,sizeof(in));q.push(1);in[1]1;dis[1]0;while(!q.empty()){int xq.front();q.pop();for(int ihead[x];i;inxt[i]){int yver[i];if(dis[x]edge[i]sdis[y]e[y]){dis[y]dis[x]edge[i]s;if(!in[y]){in[y]1;q.push(y);}}}in[x]0;}
}
void dfs(int x)
{vis[x]1;for(int ihead[x];i;inxt[i]){int yver[i];if(!vis[y]) dfs(y);}
}
bool check(int x)
{for(int i1;in;i){if(e[i]){memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));if(dfs_SPFA(i,x)) return 0;}}SPFA(x);if(dis[n]0) return 1;return 0;
}
int main()
{freopen(earth.in,r,stdin);freopen(earth.out,w,stdout);cint;while(t--){memset(e,1,sizeof(e));memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));c0;nread();mread();for(i1;im;i){int u,v,w;uread();vread();wread();insert(u,v,w);}dfs(1);for(i1;in;i){if(!vis[i]) e[i]0;}for(i1;in;i){if(e[i]){memset(vis,0,sizeof(vis));dfs(i);if(!vis[n]) e[i]0;}}int l-100000,r100000,mid,ans;while(lr){mid(lr)/2;if(check(mid)){ansdis[n];rmid-1;}else lmid1;}if(ans1e9) cout-1endl;else coutansendl;}fclose(stdin);fclose(stdout);return 0;
} 转载于:https://www.cnblogs.com/LSlzf/p/10391754.html
