https://www.patest.cn/contests/gplt/L2-001
题解：求最短路的条数，并输出点的权值最大的路径，用priority_queue会wa两个点，原因不明。
于是又学了另外一种dijkstra
坑：L3的天梯地图是同一个模板的题目，结果代码交上去有一个点过不了。。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <map>
#include<stack>
#include<set>
#include<string.h>
#define pb push_back
#define _for(i, a, b) for (int i = (a); i<(b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std;
const int N = + ; int num[N];
int E[N][N];
int dis[N];
vector<int> path;
int ans[N];
int sum[N];
int last[N];
void init() {
_for(i, , N) {
dis[i] = 1e9;
//ans[i] = 1; }
}
int main() {
init();
memset(E, -, sizeof(E));
int n;
int m, s, d;
cin >> n >> m >> s >> d;
set<int>vis;
_for(i, , n) {
cin >> num[i]; sum[i] = num[i]; vis.insert(i);
}
_for(i, , m) {
int x, y, z;
cin >> x >> y >> z;
E[x][y] = E[y][x] = z;
} last[s] = -; ans[s] = ; dis[s] = ;
for (int now = s; vis.size()>; vis.erase(now)) {
int mn = 1e9;
_for(i, , n) {
if (dis[i] < mn&&vis.count(i) == ) {
now = i;
mn = dis[i];
}
}
_for(j, , N) if(E[now][j]!=-){ if (dis[j] > dis[now] + E[now][j]) {
dis[j] = dis[now] + E[now][j];
last[j] = now;
sum[j] = sum[now] + num[j];
ans[j] = ans[now];
}
else if (dis[j] == dis[now] + E[now][j]) {
ans[j] += ans[now];
if (sum[j] < sum[now] + num[j]) {
last[j] = now;
sum[j] = sum[now] + num[j];
}
}
}
} cout << ans[d] << ' ' << sum[d] << endl;
stack<int>st;
for (int i = d; i != -; i = last[i]) {
st.push(i);
} cout << st.top(); st.pop();
while (!st.empty()) { cout << ' ' << st.top(); st.pop(); } system("pause"); }
附上wa2的代码，以后研究（求助）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <map>
#include<stack>
#define pb push_back
#define _for(i, a, b) for (int i = (a); i<(b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std;
const int N = +; int num[N];
vector< pair<int, int> > E[N];
int dis[N];
vector<int> path[N];
int ans[N];
int sum[N];
int last[N]; void init() {
_for(i, , N) {
dis[i] = 1e9;
ans[i] = ;
//last[i] = -1;
}
}
int main() {
init();
int n;
int m, s, d;
cin >> n >> m >> s >> d;
_for(i, , n) { cin >> num[i]; sum[i] = num[i]; }
_for(i, , m) {
int x, y, z;
cin >> x >> y >> z;
E[x].pb(make_pair(y, z));
E[y].pb(make_pair(x, z)); }
priority_queue<pair<int, int> >Q;
dis[s] = ;
path[s].pb(s);
Q.push(make_pair(-dis[s], s)); last[s] = -;
while (!Q.empty()) {
int now = Q.top().second;
Q.pop();
_for(i, , E[now].size()) {
int v = E[now][i].first;//about update the node,consider every step we enumerate all the nodes linked to the priority node ,if it is better put it into a vector temporarily.
if (dis[v] > dis[now] + E[now][i].second) {
dis[v] = dis[now] + E[now][i].second;
last[v] = now;
sum[v] = sum[now] + num[v];
ans[v] = ans[now];
Q.push(make_pair(-dis[v], v));
//here is the problem ,when we update dis,it's easy,but about path,we need to change the before ones
}
else if (dis[v] == dis[now] + E[now][i].second) {
ans[v] += ans[now];
if (sum[v]<sum[now]+num[v]) {
last[v] = now;
sum[v] = sum[now] + num[v];
Q.push(make_pair(-dis[v], v)
} }
}
}
cout << ans[d] << ' ' << sum[d] << endl;
stack<int> st;
for (int i = d; i != -; i = last[i]) {
st.push(i);
}
cout << st.top(); st.pop();
while (!st.empty()) { cout <<' '<< st.top(); st.pop(); }
system("pause"); }
L3的天梯地图：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <map>
#include<stack>
#include<set>
#include<string.h>
#define pb push_back
#define _for(i, a, b) for (int i = (a); i<(b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std;
const int N = + ; int num[N];
int E[N][N],R[N][N];
int dis[N];
int di[N];
vector<int> path;
int ans[N];
int sum[N];
int last[N];
void init() {
_for(i, , N) {
dis[i] = 1e9;
//ans[i] = 1;
di[i] = 1e9;
}
}
int main() {
init();
memset(E, -, sizeof(E));
int n;
int m, s, d;
cin >> n >> m;
set<int>vis;
_for(i, , n) {
sum[i] = ; vis.insert(i); num[i] = ;
}
_for(i, , m) {
int x, y, z;
cin >> x >> y >> z;
int len, tim;
cin >> len >> tim;
if (z == )
E[x][y] = E[y][x] = len;
else E[x][y] = len;
if (z == )
R[x][y] = R[y][x] = tim;
else R[x][y] = tim;
}
cin >> s >> d; _for(i, , n) {
sum[i] = ; vis.insert(i); num[i] = ;
}
last[s] = -; ans[s] = ; di[s] = ;
for (int now = s; vis.size()>; vis.erase(now)) {
int mn = 1e9;
_for(i, , n) {
if (di[i] < mn&&vis.count(i) == ) {
now = i;
mn = di[i];
}
}
_for(j, , N) if (E[now][j] != -) { if (di[j] > di[now] + R[now][j]) {
di[j] = di[now] + R[now][j];
last[j] = now;
sum[j] = sum[now] + num[j];
ans[j] = ans[now];
}
else if (di[j] == di[now] + R[now][j]) {
ans[j] += ans[now];
if (sum[j] > sum[now] + num[j]) {
last[j] = now;
sum[j] = sum[now] + num[j];
}
}
}
} stack<int> st1;
for (int i = d; i != -; i = last[i]) {
st1.push(i);
} //printf("Time = %d: ", di[d]);
//cout << st.top(); st.pop();
//while (!st.empty()) { cout << " => " << st.top(); st.pop(); }
//cout << endl; _for(i, , n) {
sum[i] = ; vis.insert(i); num[i] = ;
}
last[s] = -; ans[s] = ; dis[s] = ;
for (int now = s; vis.size()>; vis.erase(now)) {
int mn = 1e9;
_for(i, , n) {
if (dis[i] < mn&&vis.count(i) == ) {
now = i;
mn = dis[i];
}
}
_for(j, , N) if (E[now][j] != -) { if (dis[j] > dis[now] + E[now][j]) {
dis[j] = dis[now] + E[now][j];
last[j] = now;
sum[j] = sum[now] + num[j];
ans[j] = ans[now];
}
else if (dis[j] == dis[now] + E[now][j]) {
ans[j] += ans[now];
if (sum[j] > sum[now] + num[j]) {
last[j] = now;
sum[j] = sum[now] + num[j];
}
}
}
} stack<int> st2;
for (int i = d; i != -; i = last[i]) {
st2.push(i);
}
if (st1 == st2) {
printf("Time = %d; Distance = %d: ", di[d],dis[d]);
cout << st2.top(); st2.pop();
while (!st2.empty()) { cout << " => " << st2.top(); st2.pop(); }
}
else {
printf("Time = %d: ", di[d]);
cout << st1.top(); st1.pop();
while (!st1.empty()) { cout << " => " << st1.top(); st1.pop(); }
cout << endl;
printf("Distance = %d: ", dis[d]);
cout << st2.top(); st2.pop();
while (!st2.empty()) { cout << " => " << st2.top(); st2.pop(); }
cout << endl;
}
system("pause"); }