给出n个城市，m条边，起始点c1和目的点c2
接下来给出n个城市的队伍数
以及m条双向边
问你求c1到c2的所有最短路径数目，以及其中经过的最多队伍数
先最短路dijkstra，同时建立vector数组pre存储前驱节点
然后dfs求出路径，以及每条路径经过的队伍数，更新最大值即可
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <string> #include <vector> #include <queue> #define INF 0x3f3f3f using namespace std; const int maxn=505; int n,m,c1,c2; int team[maxn]; struct Edge{ int to; int w; int next; }edge[maxn*maxn]; int head[maxn]; int tot; void add(int u,int v,int w){ edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } void init(){ memset(head,-1,sizeof(head)); tot=0; } struct Node{ int u; int dis; bool operator<(const Node tmp)const{ return dis>tmp.dis; } }; int dis[maxn]; int vis[maxn]; vector<int>pre[maxn]; void dijkstra(int s,int t){ for(int i=0;i<maxn;i++){ dis[i]=INF; pre[i].clear(); vis[maxn]=0; } priority_queue<Node>q; Node tmp; tmp.u=s; tmp.dis=dis[s]=0; q.push(tmp); while(!q.empty()){ tmp=q.top(); q.pop(); vis[tmp.u]=1; int u=tmp.u; if(u==t) break; for(int k=head[u];k!=-1;k=edge[k].next){ int v=edge[k].to; if(!vis[v]){ if(dis[u]+edge[k].w<dis[v]){ dis[v]=dis[u]+edge[k].w; tmp.u=v; tmp.dis=dis[v]; q.push(tmp); pre[v].clear(); pre[v].push_back(u); } else if(dis[u]+edge[k].w==dis[v]){ /* 原先下面的没有注释掉，导致有样例错误。。。 这样会导致点v会在队列里出现两多次，也就取出多次 这样会出现重复的路径，影响最短路径数 */ //tmp.u=v; //tmp.dis=dis[v]; //q.push(tmp); pre[v].push_back(u); } } } } } vector<int>path; int maxsum=0; int cnt=0; void dfs(int u){ if(pre[u].size()==0){ path.push_back(u); cnt++; int sum=0; for(int i=0;i<path.size();i++){ int u=path[i]; sum+=team[u]; //printf("%d<-",u); } //printf(" "); if(sum>maxsum){ maxsum=sum; } path.pop_back(); return; } path.push_back(u); for(int i=0;i<pre[u].size();i++){ dfs(pre[u][i]); } path.pop_back(); } int main() { int u,v,w; init(); scanf("%d %d %d %d",&n,&m,&c1,&c2); for(int i=0;i<n;i++){ scanf("%d",&team[i]); } for(int i=0;i<m;i++){ scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,w); } dijkstra(c1,c2); dfs(c2); printf("%d %d ",cnt,maxsum); return 0; }