kuangbin最短路专题
时间：2022-09-26 21:00:01
青蛙POJ2253
传送门
在二维平面上有 n个石头。
第一块石头上有青蛙，第二块石头上有青蛙。
第一块石头上的青蛙要去第二块石头找另一只青蛙玩。
它可以直接跳到第二块石头上，也可以通过一系列中间石头跳到第二块石头上。
青蛙希望单次跳跃的最长距离尽可能短。
请计算并输出最长距离的最小可能值。
输入格式
输入包含多组测试数据。
每组数据的第一行包含一个整数 n。
接下来 n行，第 i 行包含两个整数 xi,yi，表示第 i石头的位置坐标。
每组数据输入后，还将输入空行。
当输入 n=0点，表示输入结束。
输出格式
每组数据先输出一行 Scenario #x，其中 x(从) 开始)。然后输出一行。 Frog Distance = y，其中 y保留三位小数是单次跳跃最长距离的最小可能值。
每组数据输出后，还要输出一行空行(最后一组数据也不例外)。
数据范围
2≤n≤200,0≤xi,yi≤1000。
输入样例：
2
0 0
3 4
3
17 4
19 4
18 5
0
输出样例：
Scenario #1
Frog Distance = 5.000
Scenario #2
Frog Distance = 1.414
解析
参考了 MangataTS 巨大的问题解决了，题目。QAQ
最大路径最小值问题
当前正在对起点t，终点j做一个放松的操作，所以做的不是dist[j]=max(dist[j],dist[t] w)而是dist[j]=max(dist[t],w)这样，我们就可以记录最长边，所以现在dist[i]它表示从1开始到i结束的最长边长，而不是累积长度
int n; db dist[M]; db dis( PDD a , PDD b ){
return sqrt( pow( a.first-b.first , 2 ) pow( a.second-b.second , 2 ) ); } void solve(){
vector<PDD>xoy(n); rep( i , 0 , n 1 ) dist[i] = INF; rep( i , 0 , n ) cin >> xoy[i].first >> xoy[i].second; dist[0] = 0.0; priority_queue<PDI,vector&l;PDI>,greater<PDI>>q;
q.push( {
0 , 0 } );
while( q.size() ){
auto t = q.top();
q.pop();
db len = t.first;
int st = t.second;
rep( i , 0 , n ){
db temp = max( len , dis( xoy[st] , xoy[i] ) );
if( temp < dist[i] ){
dist[i] = temp;
q.push( {
dist[i] , i } );
}
}
}
}
int main(){
int i = 1;
while( cin >> n && n ){
solve();
cout << "Scenario #" << i++ << endl;
printf("Frog Distance = %.3lf\n\n",dist[1]);
}
return 0;
}
货物运输POJ1797
传送门
给定一个 n 个点 m条边的无重边无自环的无向图。点的编号为 1∼n。
现在，要从点 1到点 n运货。
已知每条边的最大承重，请你计算一次最多可以运多少货物。
输入格式
第一行包含整数 T，表示共有 T组测试数据。
每组数据第一行包含两个整数 n,m。
接下来 m行，每行三个整数 a,b,c，表示点 a 和点 b 之间有一条无向边，最大承重为 c。
输出格式
每组数据先输出一行 Scenario #x，其中 x是组别编号（从 1开始）。然后一行，输出一个整数，表示一次性最多可运货物数量。
最后输出一个空行。
数据范围
1≤T≤10,1≤n≤1000,
1≤m≤n(n−1)2,
1≤a,b≤n,
1≤c≤106。
保证一定有解。
输入样例：
1
3 3
1 2 3
1 3 4
2 3 5
输出样例：
Scenario #1:
4
题解
最小路径最大，与上一道题目的解法相反
int n,m;
int mp[M][M],dist[M];
void solve(){
cin >> n >> m;
memset( mp , 0 , sizeof mp );
memset( dist , 0 , sizeof dist );
while( m-- ){
int u,v,w;
cin >> u >> v >> w;
mp[u][v] = w;
mp[v][u] = w;
}
dist[0] = INF;
priority_queue<PII>q;
q.push( {
INF , 1 } );
while( q.size() ){
auto t = q.top();
q.pop();
int st = t.second;
int l = t.first;
if( l < dist[st] ) continue;
rep( i , 1 , n+1 ){
if( temp > dist[i] ){
dist[i] = temp;
q.push( {
dist[i] , i } );
}
}
}
}
int main(){
int t;
scanf("%d",&t);
rep( i ,1 , t+1 ){
solve();
printf("Scenario #%d:\n",i);
printf("%d\n\n",dist[n]);
}
return 0;
}
农场派对USACO
传送门
N 头牛要去参加在某农场举行的一场编号为 X的牛的派对。有 M条有向道路，每条路长 Ti；每头牛参加完派对后都必须回到家，每头牛都会选择最短路径。
求这 N头牛的最短路径（一个来回）中最长的一条的长度。
特别提醒：可能有权值不同的重边。
输入格式
第一行包含三个整数 N,M,X。
接下来 M行，每行包含三个整数 Ai,Bi,Ti，表示有一条从 Ai 到 Bi 的路，长度为 Ti。
输出格式
共一行，一个数，表示最短路中最长的一条的长度。
数据范围
1≤N≤1000,
1≤X≤N,
1≤M≤105,
1≤Ti≤100
输入样例：
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
输出样例：
10
题解
刚刚开始时题意理解错了，做了一次假题。
题意就是让我们求出最短路。
有个小技巧，就是从终点开始跑最短路模板还一个就是反向见建图。
int n,m,x;
bool st[M];
int mp[M][M],dist[M];
int remp[M][M],redist[M];
void dijkstra( int be ){
//正向建图跑dj的含义是从终点返回的流程
dist[ be ] = 0;
rep( i , 0 , n ){
int t = -1;
for( int j = 1 ; j <= n ; j++ )
if( !st[j] && ( t == -1 || dist[j] < dist[t] ) )
t = j;
rep( j , 1 , n+1 ){
dist[j] = min( dist[j] , dist[t]+mp[t][j] );
}
st[t] = 1;
}
}
void redijkstra( int be ){
//反向建图跑dj的含义是各个起点到终点的过程
//不过在代码中写法还是从终点开始往各个点拓展的过程
redist[ be ] = 0;
rep( i , 0 , n ){
int t = -1;
for( int j = 1 ; j <= n ; j++ )
if( !st[j] && ( t == -1 || redist[j] < redist[t] ) )
t = j;
rep( j , 1 , n+1 ){
redist[j] = min( redist[j] , redist[t]+remp[t][j] );
}
st[t] = 1;
}
}
int main(){
memset( redist , 0x3f , sizeof redist );
memset( remp , 0x3f , sizeof remp );
memset( dist , 0x3f , sizeof dist );
memset( mp , 0x3f , sizeof mp );
cin >> n >> m >> x;
while( m-- ){
int u,v,w;
cin >> u >> v >> w;
mp[u][v] = min( mp[u][v] ,w );
remp[v][u] = min( remp[v][u] , w );
}
dijkstra( x );
memset( st , 0 , sizeof st );
redijkstra( x );
int ans = 0;
rep( i , 1 , n+1 ) ans = max( ans , dist[i]+redist[i] );
cout << ans;
return 0;
}
货币兑换POJ1860
某国家流通有 N 种货币，编号 1∼N。
该国家设有 M个货币兑换点，每个兑换点提供两种货币之间的兑换业务。
每个兑换点都自行设定货币兑换汇率以及服务费。
每个兑换点的基本信息可以用 6个数字 A,B,RAB,CAB,RBA,CBA 来描述，表示该兑换点提供第 A 种货币和第 B 种货币之间的相互兑换，并且从 A 兑换到 B 的兑换汇率为 RAB，服务费为 CAB，从 B 兑换到 A 的兑换汇率为 RBA，服务费为 CBA。
A到 B 的兑换汇率就是 1 单位 A 货币可以换得的 B货币的数量。服务费必须在兑换之前，先行从来源货币处扣除。
例如，如果从 A兑换 B 的兑换汇率为 29.75，服务费为 0.39，则用 100 元 A 货币可以兑换 (100−0.39)∗29.75=2963.3975 元 B货币。
一个商人目前手上有 V元 S 货币，他想要通过先将自己手中的钱进行辗转兑换，最终再次换回 S货币的方式，让自己手中的钱变得更多。
请你判断他能否做到。
输入格式
第一行包含四个数字 N,M,S,V。
接下来 M行，每行包含 6 个数字 A,B,RAB,CAB,RBA,CBA。
输出格式
如果可以做到让钱变多，则输出 YES，否则输出 NO。
数据范围
1≤S≤N≤100,
1≤M≤100,
0≤V≤1000,
汇率取值范围 [10−2,102]，
服务费取值范围 [0,100]。
输入样例：
3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00
输出样例：
YES
题解
判断是否存在从正权回路
int n, m,s;
double w[N],fee[N],v;
int h[N], e[N], ne[N], idx;
double dist[N];
bool st[N];//存储当前队列中的点，避免重复推入。
void add(int a, int b, double c , double d)
{
e[idx] = b, w[idx] = c , fee[idx] = d , ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = v;
queue<int> q;
q.push(s);
st[s] = true;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] < (dist[t]-fee[i])*w[i])
{
dist[j] = (dist[t]-fee[i])*w[i];
if( j == s ) return 1;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return 0;
}
int main()
{
scanf("%d%d%d%lf", &n, &m,&s,&v);
memset(h, -1, sizeof h);
while (m -- ){
int a, b;
double rab , cab , rba , cba;
scanf("%d%d%lf%lf%lf%lf", &a, &b, &rab, &cab, &rba, &cba);
add(a, b, rab , cab );
add( b , a , rba , cba );
}
int t = spfa();
if ( !t ) puts("NO");
else puts("YES");
return 0;
}
虫洞POJ3259
传送门
农夫约翰在巡视他的众多农场时，发现了很多令人惊叹的虫洞。
虫洞非常奇特，它可以看作是一条 单向 路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。
农夫约翰的每个农场中包含 N片田地，M 条路径（双向）以及 W个虫洞。
现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。他希望能够看到出发之前的自己。
请你判断一下约翰能否做到这一点。
下面我们将给你提供约翰拥有的农场数量 F，以及每个农场的完整信息。
已知走过任何一条路径所花费的时间都不超过 10000
秒，任何虫洞将他带回的时间都不会超过 10000秒。
输入格式
第一行包含整数 F，表示约翰共有 F个农场。
对于每个农场，第一行包含三个整数 N,M,W。
接下来 M行，每行包含三个整数 S,E,T，表示田地 S 和 E 之间存在一条路径，经过这条路径所花的时间为 T。
再接下来 W行，每行包含三个整数 S,E,T，表示存在一条从田地 S 走到田地 E 的虫洞，走过这条虫洞，可以回到 T秒之间。
输出格式
输出共 F行，每行输出一个结果。
如果约翰能够在出发时刻之前回到出发地，则输出 YES，否则输出 NO。
数据范围
1≤F≤5
1≤N≤500,
1≤M≤2500,
1≤W≤200,
1≤T≤10000,
1≤S,E≤N
输入样例：
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
输出样例：
NO
YES
spfa判断负环的模板题目
int n,m1,m2,idx,cnt[N]; int dist[N];bool st[N]; int h[N],w[N],ne[N],e[N]; void init(){ idx = 0; memset( h , -1 , sizeof h ); memset( dist , 0x3f , sizeof dist ); rep( i , 0 , n+1 ) { cnt[i] = ne[i] = e[i] = w[i] = st[i] = 0; } } void add( int u , int v , int val ){ e[idx] = v , w[idx] = val , ne[idx] = h[u] , h[u] = idx++; } bool spfa(){ queue<int>q; rep( i , 1 , n+1 ){ st[i] = 1; q.push( i ); } while( q.size() ){ int t = q.front(); q.pop(); st[t] = 0; for( int i = h[t] ; i != -1 ; i = ne[i] ){ int j = e[i]; if( dist[j] > dist[t]+w[i] ) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if( cnt[j] >= n ) return true; if( !st[j] ) { q.push( j ); st[j] = 1; } } } } return false; } string solve(){ init(); cin >> n >> m1 >> m2; rep( i , 1 , m1+1 ){ int u,v,val
