关于网站建设的介绍,电商平台怎么做,互联网信息服务,wordpress网站重定向循环H - 提瓦特之旅
原题链接#xff1a;
https://vjudge.net/contest/532518#problem/H
题意#xff1a; 一个有n个点#xff0c;m条边的无向图#xff0c;从u点到v点花费的时间和从v到u花费的时间都是C#xff08;u#xff0c;v#xff09;#xff0c;并且当经过路上的…H - 提瓦特之旅
原题链接
https://vjudge.net/contest/532518#problem/H
题意 一个有n个点m条边的无向图从u点到v点花费的时间和从v到u花费的时间都是Cuv并且当经过路上的第i个点的时候再加上额外花费的时间wi。给出q个询问每个询问给出tw1,w2,w3…wn-1询问从1到t走到第i个点额外花费的时间是wi的时候花费的最短时间
思路
求从第1个点走到第t个点经过i条边的最短距离那么经过了i条边额外的时间花费就是w1~wi
那么我们分别枚举从1到t这个点在经过i条边的条件下的最短路取最小
用bellman-Ford算法来预处理从1出发经过i条边到j的最短距离用d[i][j]表示
那么当进行每次操作的时候枚举i对d[i][t]w1…wi取最小就可以了
#include bits/stdc.h
using namespace std;
#define int long long
int d[505][505],ba[505][505];
const int INF1e16;
struct name{int a,b,w;
}q[100005];
int t,n,m;
int a[505],s[505];
void bellman(){for(int i0;in;i){for(int j0;jn;j){d[i][j]INF;}}d[0][1]0;for(int i1;in-1;i){memcpy(ba,d,sizeof d);for(int j1;jm;j){int aq[j].a ,bq[j].b ,wq[j].w;d[i][a]min(d[i][a],d[i-1][b]w);d[i][b]min(d[i][b],d[i-1][a]w);}}
}
signed main(){ios::sync_with_stdio(false);cin.tie(),cout.tie();cinnm;for(int i1;im;i){cinq[i].a q[i].b q[i].w;}bellman();cint;while(t--){int x;cinx;for(int i1;in-1;i){cina[i];s[i]s[i-1]a[i];}int ansINF;for(int i0;in-1;i){ansmin(ans,d[i][x]s[i]);}coutansendl;}return 0;
}
