倍增floyd。有点卡内存，要随着一起得出那个f。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxv 220 #define maxe 110 using namespace std; int n,m,S,E,hash[maxv],tot=0,flag=0; int f[maxv][maxv],g[maxv][maxv],h[maxv][maxv]; struct edge { int x,y,w; }eg[maxe]; int find(int x) { return lower_bound(hash+1,hash+tot+1,x)-hash; } void reset() { memset(f,0x3f,sizeof(f));memset(h,0x3f,sizeof(h)); for (int i=1;i<=tot;i++) h[i][i]=0; } void get_table() { for (int i=1;i<=m;i++) f[find(eg[i].x)][find(eg[i].y)]=f[find(eg[i].y)][find(eg[i].x)]=eg[i].w; } void get_ans() { for (int e=0;(1<<e)<=n;e++) { memset(g,0x3f,sizeof(g)); if (n&(1<<e)) { for (int k=1;k<=tot;k++) for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) g[i][j]=min(g[i][j],h[i][k]+f[k][j]); memcpy(h,g,sizeof(h)); } memset(g,0x3f,sizeof(g)); for (int k=1;k<=tot;k++) for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) g[i][j]=min(g[i][j],f[i][k]+f[k][j]); memcpy(f,g,sizeof(f)); } printf("%d ",h[find(S)][find(E)]); } int main() { scanf("%d%d%d%d",&n,&m,&S,&E); for (int i=1;i<=m;i++) { scanf("%d%d%d",&eg[i].w,&eg[i].x,&eg[i].y); hash[++tot]=eg[i].x;hash[++tot]=eg[i].y; } sort(hash+1,hash+tot+1);tot=unique(hash+1,hash+tot+1)-hash-1; reset(); get_table(); get_ans(); return 0; }