赞
踩
解题思路:使用优先队列优化的dijkstra算法
- #include<bits/stdc++.h>
- #define N 201
- #define inf 0x3f3f3f3f
- using namespace std;
- string s1,s2,s3,s4;
- int num[N],pre[N],dis[N],st,ed,cnt[N],rcnt[N],sr[N],n,vis[N];
- map<string,int> s;
- string a[N];
- struct node
- {
- int v,d;
- node()
- {
- }
- node(int v,int d):v(v),d(d)
- {
- }
- };
- vector<node> p[N];
- struct node2
- {
- int v,d;
- node2(){
- }
- node2(int v,int d):v(v),d(d){
- }
- };
- bool operator<(node2 a,node2 b)
- {
- return a.d>b.d;
- }
- priority_queue<node2> q;
- void dijkstra()
- {
- q.push(node2(st,0));
- for(int i=0;i<n;i++) dis[i]=inf;
- dis[st]=0;rcnt[st]=1;
- node2 t;
- int u,w,v;
- while(!q.empty())
- {
- t=q.top();
- q.pop();
- u=t.v;w=t.d;
- if(vis[u]) continue;
- vis[u]=1;
- for(int i=0;i<p[u].size();i++)
- {
- v=p[u][i].v;
- if(dis[v]>w+p[u][i].d)
- {
- dis[v]=w+p[u][i].d;
- q.push(node2(v,dis[v]));
- sr[v]=sr[u]+num[v];
- rcnt[v]=rcnt[u];
- cnt[v]=cnt[u]+1;
- pre[v]=u;
- }else
- if(dis[v]==w+p[u][i].d)
- {
- rcnt[v]+=rcnt[u];
- if(cnt[v]<cnt[u]+1)
- {
- cnt[v]=cnt[u]+1;
- sr[v]=sr[u]+num[v];
- pre[v]=u;
- }else
- if(cnt[v]==cnt[u]+1)
- {
- if(sr[v]<sr[u]+num[v])
- {
- sr[v]=sr[u]+num[v];
- pre[v]=u;
- }
- }
- }
- }
- }
- }
- stack<int> stk;
- int main()
- {
- //freopen("t.txt","r",stdin);
- int k,d;
- cin>>n>>k>>s1>>s2;
- s[s1]=0;a[0]=s1;
- for(int i=1;i<n;i++)
- {
- cin>>s3>>d;
- s[s3]=i;a[i]=s3;
- num[i]=d;
- }
- while(k--)
- {
- cin>>s3>>s4>>d;
- int u=s[s3],v=s[s4];
- p[u].push_back(node(v,d));
- p[v].push_back(node(u,d));
- }
- st=s[s1];
- ed=s[s2];
- pre[st]=-1;
- dijkstra();
- for(int i=ed;i!=-1;i=pre[i]) stk.push(i);
- cout<<a[stk.top()];
- stk.pop();
- while(!stk.empty())
- {
- cout<<"->"<<a[stk.top()];
- stk.pop();
- }
- cout<<endl;
- cout<<rcnt[ed]<<" "<<dis[ed]<<" "<<sr[ed];
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。