一看就是dijkstra算法的变形了。 但是还是要强调的是： 1)用邻接矩阵来表达图的时候，初始化，选择，更改的目的点都是i或者j，循环是对所有的顶点循环 2)用邻接表来表达图的时候，初始化，更改的时候是对目的链来操作，操作点位v[k][j].end,循环也是对链来循环。这个很容易错，我就把d[v[k][j].end]写成了d[j]或d[v[k][j].cost] 注意在传统的dijkstra中用邻接矩阵来求最短路径的时候还一定要注意松弛操作，初始化。最常用的无非是0x3f3f3f3f了。 而返回一般是遇到目的点就返回！（有待验证）
邻接表来解答
#include <iostream> #include <cstring> #include <vector> #include <cmath> using namespace std; const int maxn = 110; int NumVex,NumEdge; int vis[maxn]; int dis[maxn]; int start,_end,NumPeople; struct edge { int end,cost; edge(int _end=0,int _cost=0):end(_end),cost(_cost){} }; vector<edge> v[maxn]; int f() { for (int i=0;i<v[start].size();i++) { dis[v[start][i].end] = v[start][i].cost; } for (int i=0;i<NumVex-1;i++) { int tmp = -1,k; for (int j=1;j<=NumVex;j++) {if(!vis[j]&&tmp<dis[j]) {tmp = dis[j];k = j;}} vis[k] = 1; if (k== _end) return tmp; for (int j=0;j<v[k].size();j++) { if(!vis[v[k][j].end]) { int t = min(v[k][j].cost,dis[k]); dis[v[k][j].end] = max(dis[v[k][j].end],t); } } } return dis[_end]; } int main() { int t; cin>>t; while(t--) { cin>>NumVex>>NumEdge; for(int i=1;i<=NumVex;i++) v[i].clear(); for(int i=1;i<=NumEdge;i++) { int a,b,c; cin>>a>>b>>c; v[a].push_back(edge(b,c)); v[b].push_back(edge(a,c)); } memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); cin>>start>>_end>>NumPeople; dis[start] = 0; vis[start] = 1; int ans = f() - 1; if(NumPeople%ans==0) cout<<NumPeople/ans<<endl; else cout<<NumPeople/ans+1<<endl; } }邻接矩阵来解答
#include <iostream> #include <vector> #include <cstring> using namespace std; const int maxn = 200; const int INF = 0x3f3f3f3f; int map[maxn][maxn]; int vis[maxn],dis[maxn]; int nv,ne; struct edge{ int AdjV; int distance; }; int f(int st,int ed) { for (int i=1;i<=nv;i++) { vis[i]=0; dis[i]=-1; } vis[st] = 1; dis[st]=0; for(int i=1;i<=nv;i++) { if(map[st][i]!=0) { dis[i] = map[st][i]; } } for(int i=0;i<nv-1;i++) { int tmp=-1,k=st; for (int j=1;j<=nv;j++) { if(!vis[j]&&tmp<dis[j]) { tmp = dis[j]; k = j; } } //if (tmp==-1) return dis[ed]; vis[k] = 1; for (int j=1;j<=nv&&k!=st;j++) { if(!vis[j]&&dis[j]<min(map[k][j],dis[k])) { dis[j] = min(map[k][j],dis[k]); } } } return dis[ed]; //else return -1; } int main() { int t; cin>>t; while(t--) { cin>>nv>>ne; for (int i=1;i<=nv;i++) for (int j=1;j<=nv;j++) map[i][j]=0; //这里也也很重要！ for (int i=0;i<ne;i++) { int a1,a2,a3; cin>>a1>>a2>>a3; map[a1][a2] = a3; map[a2][a1] = a3; } int st,ed,N; cin>>st>>ed>>N; int ans = f(st,ed); int tmp = N/(ans-1); if(tmp*(ans-1)==N) cout<<tmp<<endl; else cout<<tmp+1<<endl; // cout<<ans<<endl; } }