无锡网站制作哪里实惠,官网建设目标,梧州网站seo,万能素材库两道最短路好题 POJ3037 手玩一下 发现每一点的速度可以直接搞出来#xff0c;就是pow(2,h[1][1]-h[i][j])*V
那么从这个点出发到达别的点的耗费的时间都是上面这个数的倒数#xff0c;然后直接跑最短路就好了 #includeiostream
#includevector
#include就是pow(2,h[1][1]-h[i][j])*V
那么从这个点出发到达别的点的耗费的时间都是上面这个数的倒数然后直接跑最短路就好了 #includeiostream
#includevector
#includealgorithm
#includecstring
#includecmath
#includequeue
using namespace std;const int N 1e510;
const int inf 0x3f3f3f3f;
const int mod 1e97;
int gcd(int a,int b){return b?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res1;while(b){if(b1)resres*a%mod;b1;aa*a%mod;}return res;}int n,q,m,v;
bool vis[1010][1010];
// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){// e[idx] b,ne[idx] h[a],w[idx] c,h[a] idx;
// }double vs[1010][1010];
double dist[1010][1010];
double h[1010][1010];void solve()
{cinvnm;for(int i1;in;i){for(int j1;jm;j){double x;cinx;h[i][j] x;vs[i][j] pow(2,x-h[1][1])/v; dist[i][j] 1e15;}}dist[1][1] 0;queuepairint,intq;q.push(make_pair(1,1));int dx[] {0,0,1,-1};int dy[] {1,-1,0,0};vis[1][1] true;while(q.size()){pairint,int t q.front();q.pop();int x t.first,y t.second;vis[x][y] false;//coutx y\n;for(int i0;i4;i){int temx xdx[i],temy ydy[i];if(temx1||temxn||temy1||temym)continue;//couttemx temy\n;if(dist[temx][temy]dist[x][y]vs[x][y]){dist[temx][temy] dist[x][y]vs[x][y];if(!vis[temx][temy]){vis[temx][temy] true;q.push(make_pair(temx,temy));}}}}printf(%.2lf,dist[n][m]);}signed main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin_;_ 1;while(_--)solve();return 0;
} HDU6714 这个dijk记数还是很有意思的你得明白folyd的含义但是别被DP的含义绕进去
每次暴力的跑每一个点的单源最短路然后当有中间点的时候你就更新一下就行了没有中间的时候D【i】【j】就是一开始的距离没有被更新还是很有趣的还是得想明白floyd的具体过程好像不懂也行 一开始我就被绕进去了一直在扣floyd 的含义来写这道发现直接按上面的做法就好了 #includebits/stdc.h
using namespace std;
using ll long long;
#define int long long
using pii pairint,int;
const int N 1e410;
const int inf 0x3f3f3f3f;
const int mod 998244353;
int gcd(int a,int b){return b?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res1;while(b){if(b1)resres*a%mod;b1;aa*a%mod;}return res;}int n,q,m;
int id[N];
int e[N],ne[N],w[N],h[N],idx;
void add(int a,int b,int c){e[idx] b,ne[idx] h[a],w[idx] c,h[a] idx;
}bool vis[N];
ll dist[N];void dijkstra(int mid)
{memset(dist,0x3f,sizeof dist);memset(vis,0,sizeof vis);memset(id,0,sizeof id);priority_queuepii,vectorpii,greaterpiiheap;heap.push({0,mid});dist[mid] 0;while(heap.size()){auto t heap.top();heap.pop();int ver t.second;if(vis[ver])continue;vis[ver] true;//coutver\n;for(int ih[ver];~i;ine[i]){int j e[i];if(dist[j]dist[ver]w[i]){dist[j] dist[ver]w[i];heap.push({dist[j],j});if(vermid)continue;id[j] max(id[ver],ver);}else if(dist[j]dist[ver]w[i]){id[j] min(id[j],max(id[ver],ver));}}}
}void solve()
{cinnm;memset(h,-1,sizeof h);idx 0;while(m--){int a,b,c;cinabc;add(a,b,c),add(b,a,c);}int ans 0;for(int i1;in;i){dijkstra(i);for(int j1;jn;j)ans (id[j]ans)%mod;//cout\n;}coutans;}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;cin_;//_ 1;while(_--)solve();return 0;
}
