赞
踩
思路不难,就是最短路+多条件判断,这里说一下很多人只得了25分的原因,就是测试点2wa的情况:大概率是更新最短路径写错了,我这里使用road数组记录的,注意如果在
#include<bits/stdc++.h> #define ll long long #define rep(i,x,y) for(int i=x; i<=y; ++i) #define per(i,x,y) for(int i=x; i>=y; --i) #define mem(a,b) memset(a,b,sizeof a) #define puk push_back #define ppk pop_back #define PLI pair<ll,int> #define PII pair<int,int> #define INF 0x3f3f3f3f using namespace std; const int N = 1e3+9; string s,e; vector<PII> g[N]; int dis[N],cnt[N],ma[N],last[N]; int road[N],sum; int idx=1; bool st[N]; unordered_map<string,int> mp; struct City{ string name; int num; }city[N]; struct Node{ int dis,u; bool operator<(const Node &t) const{ if(dis!=t.dis) return dis>t.dis; } }; void Dijkstra(int S){ mem(dis,0x3f); priority_queue<Node> q; q.push({0,S}); road[S]=1; dis[S]=0; while(q.size()){ auto tmp = q.top(); q.pop(); int u = tmp.u; if(st[u]) continue; st[u]=true; for(auto &it :g[u]){ int j = it.second, w=it.first; if(dis[j]>dis[u]+w){ road[j]=road[u];//注意这里不能是road[j]+=road[u],因为到j目前只有唯一一条最短路径 dis[j]=dis[u]+w;//更新距离 cnt[j]=cnt[u]+1;//更新解放城市数量 ma[j] = ma[u] + city[j].num;//更新杀敌数量 last[j]=u; q.push({dis[j],j}); } else if(dis[j]==dis[u]+w){ //更新最短路径条数,注意是 += road[j]+=road[u]; if(cnt[j]<cnt[u]+1){ cnt[j]=cnt[u]+1;//更新解放城市数量 ma[j] = ma[u] + city[j].num;//更新杀敌数量 last[j]=u; //if(j==mp[e]) sum=ma[j]; q.push({dis[j],j}); } else if(cnt[j]==cnt[u]+1&&ma[j]<ma[u]+city[j].num){ ma[j] = ma[u] + city[j].num;//更新杀敌数量 last[j]=u; //if(j==mp[e]) sum=ma[j]; q.push({dis[j],j}); } } } } } void print(int p){ if(!p) return ; print(last[p]); sum+=city[p].num; if(last[p]) cout<<"->"; cout<<city[p].name;; } int main(){ int n,k; cin>>n>>k>>s>>e; city[1].name=s,city[1].num=0; mp[s]=1; rep(i,2,n) { cin>>city[i].name>>city[i].num; mp[city[i].name]=i; } while(k--){ string a,b; cin>>a>>b; int d; cin>>d; g[mp[a]].puk({d,mp[b]}); g[mp[b]].puk({d,mp[a]}); } Dijkstra(1); print(mp[e]); puts(""); cout<<road[mp[e]]<<" "<<dis[mp[e]]<<" "<<sum; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。