)
要准备的数组G[][] 图用邻接矩阵存储,初始化为无穷大自己到自己初始化为0dist[] 存储顶点到source的距离初始化为无穷大pre[]存储顶点的前驱结点用来输出路径用初始化为-1vis[]用来表示顶点已被收录到集合S中初始化为falsenum[]用来存储最短路径的条数初始化为0Weight[]存每个点救援队的数目即点权直接读入题目给的数据即可无须初始化W[]用来存储source到顶点这条路径上救援队的总数量初始化为0。本题基本思路就是Dijkstra算法只不过这个题增加了点权并且要记录最短路径的长度。因此在dist[]相同的时候要看一下救援队数量会不会增加。如果会增加就要更新救援队的数量W[], 前驱数组pre[], 最短路径的条数num[]。如果救援队的数量不增加记得也要更新最短路径的条数在这里犯过错误导致测试点1没通过)。Dijkstra算法进入后先要对源点的相关数据进行初始化dist[S] 0; pre[S] -1; num[S] 1因为自己到自己只有一条路,陈姥姥mooc上教的W[S] Weight[S];注意不要初始化vis[S]为true,因为后面的第一次循环会处理S。初始化完成后就可以进入常规的Dijkstra操作了。先找未被收录的最小的dist[]然后把它收录到集合S中再检查一下收录到S后会不会影响它的一圈邻接点如果会的话进行相应的更新即可。下面是这个题的代码#includestdio.h #includestack #define INF 10000000 using namespace std; #define MAXV 505 int n, G[MAXV][MAXV]; int dist[MAXV]; int pre[MAXV]; bool vis[MAXV] {false}; int num[MAXV];//路径的数目 int Weight[MAXV];//点权 int W[MAXV];//从原点到某个顶点的城市救援队的数目 void Dijkstra(int S) { int i,j,k,z; int MinDist,MinV; /*对数据进行必要的基础准备*/ dist[S] 0; pre[S] -1; num[S] 1; W[S] Weight[S]; /*下面正式进入Dijkstra*/ for(i0; in; i) { MinDist INF; MinV -1; for(j0; jn; j)//找到未被访问过的dist[] { if(vis[j]falsedist[j]MinDist) { MinDist dist[j]; MinV j; } } if(MinV -1) return; /*没有退出循环说明找到了继续执行后面的步骤*/ vis[MinV] true; for(k0; kn; k) { if(G[MinV][k]INFvis[k]false) { if(dist[MinV]G[MinV][k] dist[k]) { dist[k] dist[MinV] G[MinV][k]; pre[k] MinV; num[k] num[MinV]; W[k] W[MinV] Weight[k]; } else if((dist[MinV]G[MinV][k]dist[k])(W[MinV]Weight[k]W[k])) { pre[k] MinV; num[k] num[MinV] num[k]; W[k] W[MinV] Weight[k]; } else if(dist[MinV]G[MinV][k]dist[k]) num[k] num[MinV] num[k]; } } } } int main() { int N,M,S,D; int i,j; scanf(%d %d %d %d,N,M,S,D); for(i0; iN; i) { scanf(%d,Weight[i]); } int V1,V2,L; /*初始化*/ n N; for(i0; in; i) for(j0; jn; j) { G[i][j] INF; } /*初始化*/ for(i0; iM; i) { scanf(%d %d %d,V1,V2,L); G[V1][V2] L; G[V2][V1] L; } for(i0; in; i) { pre[i] -1; num[i] 0; dist[i] INF; W[i] 0; G[i][i] 0; } /*初始化*/ Dijkstra(S); stackint q; int path; printf(%d %d\n,num[D],W[D]); while(D!-1) { q.push(D); D pre[D]; } int count q.size(); for(i0; icount-1; i) { path q.top(); q.pop(); printf(%d ,path); } printf(%d,q.top()); return 0; }
