ダ 関節点 木の直径　長方形dp

ダイクストラろくなライブラリなかったので

```c++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
ll mypow(ll x, ll n, ll m) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return mypow(x*x%m, n / 2, m);
	}
	else {
		return x * mypow(x, n - 1, m) % m;
	}
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
///////////////////////////////////////
int ans[2010];
int d[2010];
int main() {
	int N, X, Y; cin >> N >> X >> Y;
	X--, Y--;
	vector<int>G[2010];
	for (int i = 0; i < N - 1; ++i) {
		G[i].push_back(i + 1);
		G[i + 1].push_back(i);
	}
	G[X].push_back(Y);
	G[Y].push_back(X);
	REP(i, 2010)ans[i] = 0;
	REP(i, N) {
		REP(j, N) {
			d[j] = INF;
		}
		d[i] = 0;
		priority_queue<pii, vector<pii>, greater<pii>>que;
		que.push({ 0,i });
		while (!que.empty()) {
			pii p = que.top(); que.pop();
			int v = p.second;
			if (d[v] < p.first)continue;
			for (int j = 0; j < G[v].size(); ++j) {
				if (d[G[v][j]] > d[v] + 1) {
					d[G[v][j]] = d[v] + 1;
					que.push({ d[G[v][j]],G[v][j] });
				}
			}
		}
		for (int j = 0; j < N ; ++j) {
			if (i == j)continue;
			ans[d[j]]++;
		}
	}
	for (int i = 1; i < N; ++i) {
		cout << ans[i]/2 << endl;
	}
	return 0;
}
```
これはabc 160 dで全頂点からダイクストラするやつ

```c++
int d[2010];
vector<int>G[2010];
int N, X, Y;
void dijkstra(int n) {
	priority_queue<pii,vector<pii>,greater<pii>>que;
	que.push({ 0,n });
	d[n] = 0;
	while (!que.empty()) {
		pii x = que.top();
		que.pop();
		for (int i : G[x.second]) {
			if (d[i] == INF) {
				d[i] = min(d[i], d[x.second] + 1);
				que.push({d[i],i});
			}
			else {
				d[i] = min(d[i], d[x.second] + 1);
			}
		}
	}
}
```
ダイクストラの経路の個数数え上げ


```c++
int n, m;
vector<int>G[200010];
int d[200010];
int c[200010];
int main() {
	cin >> n >> m;
	for (int i = 0; i < 200010; ++i) {
		d[i] = INF;
		c[i] = 0;
	}
	d[0] = 0;
	c[0] = 1;
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >>  b;
		a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	priority_queue<pii, vector<pii>, greater<pii>> que;
	que.push({ 0,0 });
	while (!que.empty()) {
		pii p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) {
			continue;
		}
		for (int e : G[v]) {  // 頂点vから出る辺eを走査
			if (d[e] > d[v] + 1) {
				d[e] = d[v] + 1;
				que.push({ d[e], e });
				c[e] = c[v];  // コストが更新された場合は直前の頂点への最短経路数で上書き
			}
			else if (d[e] == d[v] + 1) {
				c[e] += c[v];  // コストが一致する場合はこれまでの最短経路数を足し合わせ
			}
			c[e] %= INF;
		}
	}
	cout << c[n - 1]%INF << endl;
	return 0;
}

```
past j 
各マスごとにコストが違う時の上手い感じの実装法

```c++

int h, w;
int a[51][51];
void dijkstra(int s, int t, int d[55][55]) {
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			d[i][j] = INF;
		}
	}
	d[s][t] = 0;
	priority_queue<Pi, vector<Pi>, greater<Pi>>que;
	que.push({ 0,{s,t}});
	while(!que.empty()) {
		Pi p = que.top(); que.pop();
		int x = p.second.first, y = p.second.second;
		if (d[x][y] < p.first)continue;
		for (int k = 0; k < 4; ++k) {
			int x1= x + dx[k], y1 = y + dy[k];
			if (!check(x1, y1))continue;
			if (d[x1][y1] > d[x][y] + a[x1][y1]) {
			    d[x1][y1] = d[x][y] + a[x1][y1];
				que.push({ d[x1][y1],{x1,y1} });
			}
		}
	}
}
int main() {
	cin >> h >> w;
	REP(i, h) {
		REP(j, w) {
			cin >> a[i][j];
		}
	}
	int d[3][55][55];
	dijkstra(h - 1, 0, d[0]);
	dijkstra(h - 1, w - 1, d[1]);
	dijkstra(0, w - 1, d[2]);
	int ans = INF;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			ans = min(ans, d[0][i][j] + d[1][i][j] + d[2][i][j] - 2 * a[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}
```

abc 164 E　拡張ダイクストラ

```c++
//dp[v][s]:=頂点vにいて所持金sという状態になるのに要する最小の所要時間
ll dp[51][2525];
int main(){
	int n, m, s; cin >> n >> m >> s;
	vector<pii>G[51];
	int a[101], b[101];
	for (int i = 0; i < m; ++i) {
		int u, v; cin >> u >> v >> a[i] >> b[i];
		u--, v--;
		G[u].push_back({ v,i });
		G[v].push_back({ u,i });
		//運賃と時間を番号iで管理
	}
	int c[55], d[55];
	REP(i, n)cin >> c[i] >> d[i];
	const int mx = 2500;
	s = min(s, mx);
	const ll inf = 1e18;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= mx; ++j) {
			dp[i][j] = inf;
		}
	}
	using pI = pair<ll, pii>;
	priority_queue<pI,vector<pI>,greater<pI>>que;
	dp[0][s] = 0;
	que.push({ 0,{0,s} });
	//{時間,{場所,所持金}}
	while (!que.empty()) {
		auto p = que.top();
		que.pop();
		int x = p.second.first, y = p.second.second;
		if (p.first > dp[x][y])continue;//ここを入れ忘れないように
		int y1 = min(mx, y + c[x]);
		if (dp[x][y1] > dp[x][y] + d[x]) {
			dp[x][y1] = dp[x][y] + d[x];
			que.push({ dp[x][y1],{x,y1} });
		}
		for (auto q : G[x]) {
			int x1 = q.first, k = q.second;
			if (y < a[k])continue;
			if (dp[x1][y - a[k]] > dp[x][y] + b[k]) {
				dp[x1][y - a[k]] = dp[x][y] + b[k];
				que.push({ dp[x1][y - a[k]],{x1,y - a[k]} });
			}
		}
	}
	for (int i = 1; i < n; ++i) {
		ll ans = inf;
		for (int j = 0; j <= mx; ++j) {
			ans = min(ans, dp[i][j]);
		}
		cout << ans << endl;
	}
	return 0;
}
```
ex hopscotch addict

```c++
int dp[3][100010];
//dp[i][j]で頂点jにi(mod 3)回のけんけんでたどり着く時の最小回数
int main(){
	int N, M; cin >> N >> M;
	Graph G;
	G.resize(N);
	REP(i, M) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		G[u].push_back(v);
	}
	int S, T; cin >> S >> T;
	S--, T--;
	priority_queue<Pi, vector<Pi>, greater<Pi>>que;
	que.push({ 0,{S,0} });
	REP(i, 3)REP(j, 100010)dp[i][j] = INF;
	dp[0][S] = 0;
	//{回数,{場所,mod3}}
	while (!que.empty()) {
		auto a = que.top();
		int x = a.second.first;
		int y = a.second.second;
		que.pop();
		if (a.first > dp[y][x])continue;
		for (int q : G[x]) {
			if (dp[(y + 1) % 3][q] > dp[y][x]+1) {
				dp[(y + 1) % 3][q] = dp[y][x] + 1;
				que.push({ dp[(y + 1) % 3][q],{q,(y + 1) % 3} });
			}
		}
	}
	if (dp[0][T] == INF) {
		cout << -1 << endl;
	}
	else {
		cout << dp[0][T]/3 << endl;
	}
	return 0;
}
```
ほぼ同じように解ける

関節点

```cpp
vector<int>G[100010];
int N;
bool visited[100010];
int prenum[100010], parent[100010], lowest[100010], timer;
void dfs(int current, int prev) {
	prenum[current] = lowest[current] = timer;
	timer++;
	visited[current] = true;
	int next;
	for (int i = 0; i < G[current].size(); ++i) {
		next = G[current][i];
		if (!visited[next]) {
			parent[next] = current;
			dfs(next, current);
			lowest[current] = min(lowest[current], lowest[next]);
		}
		else if (next!=prev) {
			lowest[current] = min(lowest[current], prenum[next]);
		}
	}
}
void art_points() {
	for (int i = 0; i < N; ++i)visited[i] = false;
	timer = 1;
	dfs(0, -1);
	set<int>ap;
	int np = 0;
	for (int i = 1; i < N; ++i) {
		int p = parent[i];
		if (p == 0)np++;
		else if (prenum[p] <= lowest[i])ap.insert(p);
	}
	if (np > 1)ap.insert(0);
	for (set<int>::iterator it = ap.begin(); it != ap.end(); ++it) {
		cout << *it << endl;
	}
}
int main() {
	int m;
	cin >> N >> m;
	for (int i = 0; i < m; ++i) {
		int s, t;
		cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
	}
	art_points();
	return 0;
}
```
木の直径

```cpp
vector<pii>G[100010];
int n, d[100010];
bool vis[100010];
int cnt;

void bfs(int s) {
	for (int i = 0; i < n; ++i) {
		d[i] = INF;
	}
	queue<int>Q;
	Q.push(s);
	d[s] = 0;
	int u;
	while (!Q.empty()) {
		u = Q.front(); Q.pop();
		for (int i = 0; i < G[u].size(); ++i) {
			pii e = G[u][i];
			if (d[e.second] == INF) {
				d[e.second] = d[u] + e.first;
				Q.push(e.second);
			}
		}
	}
}
void solve() {
	//適当な始点sから最も遠い節点tgtを求める
	bfs(0);
	int maxv = 0;
	int tgt = 0;
	for (int i = 0; i < n; ++i) {
		if (d[i] == INF)continue;
		if (maxv < d[i]) {
			maxv = d[i];
			tgt = i;
		}
	}
	bfs(tgt);
	maxv = 0;
	for (int i = 0; i < n; ++i) {
		if (d[i] == INF) {
			continue;
		}
		maxv = max(maxv, d[i]);
	}
	cout << maxv << endl;
}
int main() {
	int s, t, w;
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		cin >> s >> t >> w;
		G[s].push_back({ w,t });
		G[t].push_back({ w,s });
	}
	solve();
	return 0;
}
```