POJ3613

---

題意：n條邊構成的最短路

做法：倍增floyd

#include <cstdio> #include <cstring> #include <algorithm> #define rep(i,a,b) for(int i=a;i<=b;++i) typedef long long ll; const int N = 207; const int inf = 0x3f3f3f3f; using namespace std; int n,cnt,id[1007],T,S,E; int dis[N][N][25],d[N][N],tmp[N][N];// dis[i][j][k] : i -> j 經過 2^k 條邊的最短路int main() {scanf("%d%d%d%d",&n,&T,&S,&E);rep(i,1,200)rep(j,1,200)rep(k,0,22) dis[i][j][k] = d[i][j] = inf;rep(i,1,T) {int x,y,z;scanf("%d %d %d",&z,&x,&y);if(!id[x]) id[x] = ++cnt;if(!id[y]) id[y] = ++cnt;dis[id[x]][id[y]][0] = dis[id[y]][id[x]][0] = min(z,dis[id[y]][id[x]][0]);}rep(s,1,20)rep(k,1,cnt)rep(i,1,cnt)rep(j,1,cnt){dis[i][j][s] = min(dis[i][j][s],dis[i][k][s-1]+dis[k][j][s-1]);}rep(i,1,cnt) d[i][i] = 0;rep(s,0,20)if(n&(1<<s)) {rep(i,1,cnt)rep(j,1,cnt) tmp[i][j]=inf;rep(k,1,cnt)rep(i,1,cnt)rep(j,1,cnt) {tmp[i][j] = min(tmp[i][j],d[i][k]+dis[k][j][s]);}rep(i,1,cnt)rep(j,1,cnt)d[i][j]=tmp[i][j];}printf("%d\n",d[id[S]][id[E]]);return 0; }

轉載于:https://www.cnblogs.com/RRRR-wys/p/9432069.html

總結

以上是生活随笔為你收集整理的POJ3613的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。