L3-011 直捣黄龙 (30 分)——25分，测试点2错误分析_l3-011 直捣黄龙 测试点2

题目链接

思路

思路不难，就是最短路+多条件判断，这里说一下很多人只得了25分的原因，就是测试点2wa的情况：大概率是更新最短路径写错了，我这里使用road数组记录的，注意如果在

• 更新最短距离时更新路径条数，应该是 $road[j]=road[u]$
• 更新两外两种情况时更新路径条数，应该是 $road[j]+=road[u]$

AC代码

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104