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 = 500 + 5; 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, 0, N) { dis[i] = 1e9; //ans[i] = 1; } } int main() { init(); memset(E, -1, sizeof(E)); int n; int m, s, d; cin >> n >> m >> s >> d; set<int>vis; _for(i, 0, n) { cin >> num[i]; sum[i] = num[i]; vis.insert(i); } _for(i, 0, m) { int x, y, z; cin >> x >> y >> z; E[x][y] = E[y][x] = z; } last[s] = -1; ans[s] = 1; dis[s] = 0; for (int now = s; vis.size()>0; vis.erase(now)) { int mn = 1e9; _for(i, 0, n) { if (dis[i] < mn&&vis.count(i) == 1) { now = i; mn = dis[i]; } } _for(j, 0, N) if(E[now][j]!=-1){ 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 != -1; 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 = 500+5; 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, 0, N) { dis[i] = 1e9; ans[i] = 1; //last[i] = -1; } } int main() { init(); int n; int m, s, d; cin >> n >> m >> s >> d; _for(i, 0, n) { cin >> num[i]; sum[i] = num[i]; } _for(i, 0, 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] = 0; path[s].pb(s); Q.push(make_pair(-dis[s], s)); last[s] = -1; while (!Q.empty()) { int now = Q.top().second; Q.pop(); _for(i, 0, 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 != -1; 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 = 500 + 5; 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, 0, N) { dis[i] = 1e9; //ans[i] = 1; di[i] = 1e9; } } int main() { init(); memset(E, -1, sizeof(E)); int n; int m, s, d; cin >> n >> m; set<int>vis; _for(i, 0, n) { sum[i] = 1; vis.insert(i); num[i] = 1; } _for(i, 0, m) { int x, y, z; cin >> x >> y >> z; int len, tim; cin >> len >> tim; if (z == 0) E[x][y] = E[y][x] = len; else E[x][y] = len; if (z == 0) R[x][y] = R[y][x] = tim; else R[x][y] = tim; } cin >> s >> d; _for(i, 0, n) { sum[i] = 1; vis.insert(i); num[i] = 1; } last[s] = -1; ans[s] = 1; di[s] = 0; for (int now = s; vis.size()>0; vis.erase(now)) { int mn = 1e9; _for(i, 0, n) { if (di[i] < mn&&vis.count(i) == 1) { now = i; mn = di[i]; } } _for(j, 0, N) if (E[now][j] != -1) { 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 != -1; 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, 0, n) { sum[i] = 1; vis.insert(i); num[i] = 1; } last[s] = -1; ans[s] = 1; dis[s] = 0; for (int now = s; vis.size()>0; vis.erase(now)) { int mn = 1e9; _for(i, 0, n) { if (dis[i] < mn&&vis.count(i) == 1) { now = i; mn = dis[i]; } } _for(j, 0, N) if (E[now][j] != -1) { 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 != -1; 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"); }