---

图专题1(PAT)：

1.紧急情况

紧急情况

 

2.旅行计划

旅行计划

 

3.团伙头目

团伙头目

 

4.条条大路通罗马

条条大路通罗马

 

5.在线地图

在线地图

 

6.哈密顿回路

哈密顿回路

 

7.欧拉路径

欧拉路径

 

8.地铁地图

地铁地图

 

9.顶点覆盖

顶点覆盖

 

AC代码:

1.紧急情况

/*
  注意到递推关系: 
    如果0->5 有两条最短路:
      0 -> 2 -> 6 -> 5
      0 -> 3 -> 4 -> 5
      对于最短路条数的递推关系: cnt[5] = cnt[4] + cnt[6];
      对于最多收集救援数量的递推关系: team[5] = max(max_team[4],max_team[6]) + num_team[5] 到达4和6的所有最短路径中收集到的最多队伍+本身队伍
    这个递推关系是一个简单的线性dp关系,只是要按照寻找最短路的搜索顺序就要利用dijkstra算法
*/
# include <iostream>
# include <queue>
# include <vector>
# include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
const int M = 610;

struct DATA{
  int h = -1;
  bool flag = false;
  int max_team = 0;
  int num_team;
  int cnt = 0;
  int dist = 2e9;
}h[N];

int ne[M * 2],e[M * 2],w[M * 2],idx = 0,n,m;

...