PAT 甲级(Advanced Level) 1002 A+B for Polynomials (25 分)
思路:无向图的最短路径问题,Dijkstra一波带走。
《算法笔记》里面的Dijkstra讲得比较好,严重推荐。
心得:这种题目最好直接画个图,好理清思路,样例图如下:
答案显然是 0-2 和 0-1-2两条最短路径,最大teams数量4个。
改进的话用Dijkstra+priority_queue。另外如果是针对PAT考试的话,
最短路径还是多写写,因为考试不能带资料(略坑)。
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
const int MAX = 501;
const int INF = 0x3fffffff;
int n, m, st, ed;
int G[MAX][MAX];
bool vis[MAX] = {false};
int d[MAX];
int weight[MAX];
int w[MAX];
int nums[MAX];
void dijkstra(int s){
fill(d, d+MAX, INF);
nums[s] = 1;
w[s] = weight[s];
d[s] = 0;
for(int i = 0; i < n; ++i){
int u = -1, MIN = INF;
for(int j = 0; j < n; ++j){
if(vis[j] == false && d[j] < MIN){
MIN = d[j];
u = j;
}
}
if(u == -1)
return;
vis[u] = true;
for(int v = 0; v < n; ++v){
if(vis[v] == false && G[u][v] != INF){
if(d[u] + G[u][v] < d[v]){
d[v] = d[u] + G[u][v];
w[v] = w[u] + weight[v];
nums[v] = nums[u];
}
else if(d[u] + G[u][v] == d[v]){
nums[v] += nums[u];
if(w[u] + weight[v] > w[v])
w[v] = w[u] + weight[v];
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m >> st >> ed;
fill(G[0], G[0]+MAX*MAX, INF);
for(int i = 0; i < n; ++i)
cin >> weight[i];
for(int j = 0; j < m; ++j){
int c1, c2, l;
cin >> c1 >> c2 >> l;
G[c1][c2] = G[c2][c1] = l;
}
dijkstra(st);
cout << nums[ed] << ' ' << w[ed];
return 0;
}