PAT 甲级 总结 —— 高级篇

PAT 甲级 总结 —— 高级篇
一、最短路径
PAT中30分的常考题型，主要有Dijkstra算法、Floyd算法、Bellman-Ford算法(暂时未考)
dijkstra：无负边权单源最短路径问题万能通法，可以回溯路径，选取多条件最优路径
struct node {
int v, w;
};
int dis[maxn];
vector pre[maxn];
vector adj[maxn];

void Dijkstra(int s)
{
fill(dis, dis + maxn, INF);
dis[s] = 0;
for (int i = 0; i < n + 1; i++) { int min = INF, u = -1; for (int j = 0; j < n + 1; j++) { if (!vis[j] && min > dis[j]

PAT 甲级 总结 —— 高级篇最先出现在Python成神之路。