点击打开pat链接
#include<iostream> #include<math.h> #include<algorithm> #include<queue> #include<map> #include<stack> #include<string> #include<vector> using namespace std; #define INF 100000000 #define maxn 100010 struct edge{ int end,weight; }; struct node{ int pop; vector<edge> bian; }; vector<node> ad; int w[maxn];//记录点权之和 int pre[maxn]; int vt[maxn]; vector<int> result; int accord[maxn];//记录到到每个点最短路径的条数 bool visit[maxn]={false}; void Dji(int v,int num){ fill(vt,vt+num,INF); fill(w,w+num,0); fill(accord,accord+num,0); vt[v]=0; accord[v]=1; w[v]=ad[v].pop; // cout<<w[v]; for(int i=0;i<num;i++) { int u=-1,store=INF; for(int j=0;j<num;j++) { if(vt[j]<store&&visit[j]==false){ u=j; store=vt[j]; } } if(u==-1) return; visit[u]=true; for(int k=0;k<ad[u].bian.size();k++) { int z; z=ad[u].bian[k].end; if(visit[z]==false){ if(vt[u]+ad[u].bian[k].weight<vt[z]) { vt[z]=vt[u]+ad[u].bian[k].weight; accord[z]=accord[u]; w[z]=w[u]+ad[z].pop;} else if(vt[u]+ad[u].bian[k].weight==vt[z]) { if(w[u]+ad[z].pop>w[z]) w[z]=w[u]+ad[z].pop; accord[z]+=accord[u]; //注意路径的写法 } } } } } int main() {int city,c1,c2,num; cin>>city>>num>>c1>>c2; int pop; for(int i=0;i<city;i++) { node temp; cin>>pop; temp.pop = pop; ad.push_back(temp); } for (int i = 0; i < num; i++) { int start, end, weight; cin >> start >> end >> weight; edge qw; qw.end = end; qw.weight = weight; ad[start].bian.push_back(qw); qw.end=start; ad[end].bian.push_back(qw); } Dji(c1,city); /*for(int i=0;i<ad[4].bian.size();i++) cout<<ad[4].bian[i].end<<" "<<ad[4].bian[i].weight<<endl;*/ cout<<accord[c2]<<" "<<w[c2]; return 0; }
