图论的题目整合（Dijkstra）

前置知识：
Dijkstra

题目1

AT_abc070_d [ABC070D] Transit Tree Path
由于点 $K$ 是固定的，并且是无向图（题目说是树），其实可以理解为求点 $K$ 到点 x j x_j xj​ 的最短路加上点 $K$ 到点 y j y_j yj​ 的最短路。

由于边权 c i c_i ci​ 的范围是 1≤ c i ≤1 0 9 1\\le c_i\\le10^9 1≤ci​≤109，没有负数，所以用 Dijkstra 以 $K$ 为起点跑最短路。

#include#define int long long#define endl putchar(\'\\n\')using namespace std;const int N=1e6+5;int read(){int x=0,f=1;char c=getchar();while(c<\'0\'||c>\'9\'){if(c==\'-\')f=-1;c=getchar();}while(c>=\'0\'&&c<=\'9\')x=(x<<3)+(x<<1)+c-\'0\',c=getchar();return x*f;}void print(int x){if(x<0)putchar(\'-\'),x=-x;if(x<10){putchar(x+\'0\');return;}print(x/10);putchar(x%10+\'0\');}int n,m,k;int T;struct node{int to,dis;friend bool operator <(node a,node b){return a.dis>b.dis;}};priority_queue<node>q;vector<node>a[N];int dis[N];int vis[N];void dij(){for(int i=1;i<=n;i++)dis[i]=1e18;dis[k]=0;q.push(node{k,0});while(!q.empty()){node t=q.top();q.pop();int x=t.to;if(vis[x])continue;vis[x]=1;for(int i=0;i<a[x].size();i++){int y=a[x][i].to;int z=a[x][i].dis;dis[y]=min(dis[y],dis[x]+z);if(!vis[y])q.push(node{y,dis[y]});}}}signed main(){n=read();m=n-1;while(m--){int u=read(),v=read(),w=read();a[u].push_back(node{v,w});a[v].push_back(node{u,w});}T=read(),k=read();dij();while(T--){int x=read(),y=read();print(dis[x]+dis[y]);endl;}}

题目2

题目描述
给出 $N$ 个结点，$M$ 条边的有向图，结点从 $1$ 到 $M$ 编号。
求最少将多少条边反向，才能至少有一条从 $1$ 到 $N$ 的路径？
例如，下图中把 $3⟶2,7⟶4$ 这两条边反向，可以得到一条从 $1$ 到 $7$ 的路径。
也可以把 $6⟶2,5⟶6,7⟶5$ 这三条边反向，得到一条从 $1$ 到 $7$ 的路径。
显然前者更优。
输入格式
第 $1$ 行：$N$ 和 $M$。
接下来 $M$ 行，每行 $2$ 个整数 $u,v$，表示一条有向边。
输出格式
第 $1$ 行：$1$ 个整数，表示答案。
如果无法实现从 $1$ 到 $N$，输出 $-1$。

反转一条边需要一次，所以可以建一条翻转后的边但是边权为 $1$，再对图跑最短路（或者01BFS）。

#include#define int long longusing namespace std;const int N=1e6+5;int read(){int x=0,f=1;char c=getchar();while(c<\'0\'||c>\'9\'){if(c==\'-\')f=-1;c=getchar();}while(c>=\'0\'&&c<=\'9\')x=(x<<3)+(x<<1)+c-\'0\',c=getchar();return x*f;}void print(int x){if(x<0)putchar(\'-\'),x=-x;if(x<10){putchar(x+\'0\');return;}print(x/10);putchar(x%10+\'0\');}void putstr(string s){for(char v:s)putchar(v);}int n,m;struct node{int to,dis;friend bool operator<(node a,node b){return a.dis>b.dis;}};vector<node>a[N];int dis[N];int vis[N];priority_queue<node>q;signed main(){n=read(),m=read();while(m--){int u=read(),v=read();a[u].push_back(node{v,0});a[v].push_back(node{u,1});}for(int i=1;i<=n;i++)dis[i]=1e18;q.push(node{1,0});dis[1]=0;while(!q.empty()){int x=q.top().to;q.pop();if(vis[x])continue;vis[x]=1;for(int i=0;i<a[x].size();i++){int y=a[x][i].to;int z=a[x][i].dis;if(dis[y]>dis[x]+z)dis[y]=dis[x]+z;if(!vis[y])q.push(node{y,dis[y]});}}if(dis[n]>=1e18)dis[n]=-1;print(dis[n]);}

题目3

题目描述
给出一个有 $n$ 个顶点 $m$ 条边的无向连通图，每条边有一个长度 L i L_i Li​，结点编号从 $1\sim n$。
求从起点 $1$ 到终点 $n$ 的最短路径的长度及其途经的各结点。
输入格式
第 $1$ 行：$2$ 个整数 $n$ 和 $m(n\le 200,m\le 10000)$。
接下来 $m$ 行，每行 $3$ 个整数 x,y, L i x, y, L_i x,y,Li​，表示结点 $x$ 和 $y$ 之间的长度为 L i L_i Li​。
输出格式
第 $1$ 行：$1$ 个整数，表示 $1$ 到 $n$ 的最短距离。
第 $2$ 行：若干个整数，表示 $1$ 到 $n$ 的最短路径经过的各结点。

根据单源最短路径改，每次找到更优的路径就标记一下它下一个点的上一个点，注意不能标记下一个点来记录路径，因为起点不止能到终点 $n$，但是终点 $n$ 只能是起点到达。

#include#define int long long//#define lc p<<1//#define rc p<<1|1//#define lowbit(x) x&-x#define psp putchar(\' \')#define endl putchar(\'\\n\')using namespace std;const int N=1e6+5;int read(){int x=0,f=1;char c=getchar();while(c<\'0\'||c>\'9\'){if(c==\'-\')f=-1;c=getchar();}while(c>=\'0\'&&c<=\'9\')x=(x<<3)+(x<<1)+c-\'0\',c=getchar();return x*f;}void print(int x){if(x<0)putchar(\'-\'),x=-x;if(x<10){putchar(x+\'0\');return;}print(x/10);putchar(x%10+\'0\');}void putstr(string s){for(char v:s)putchar(v);}int n,m,s;int T;struct node{int to,dis;friend bool operator <(node a,node b){return a.dis>b.dis;}};priority_queue<node>q;vector<node>a[N];int dis[N];int vis[N];int pre[N];void dij(){for(int i=1;i<=n;i++)dis[i]=INT_MAX;dis[1]=0;q.push(node{1,0});while(!q.empty()){node t=q.top();q.pop();int x=t.to;if(vis[x]==1)continue;vis[x]=1;for(int i=0;i<a[x].size();i++){int y=a[x][i].to;int z=a[x][i].dis;if(dis[y]>dis[x]+z){dis[y]=dis[x]+z;pre[y]=x;}if(vis[y]==0)q.push(node{y,dis[y]});}}}signed main(){n=read(),m=read();for(int i=1;i<=m;i++){int u=read(),v=read(),w=read();a[u].push_back(node{v,w});a[v].push_back(node{u,w});}dij();print(dis[n]),endl;stack<int>t;while(n){t.push(n);n=pre[n];}while(!t.empty()){print(t.top()),psp;t.pop();}}

题目4

题目描述
$N(1\le N\le 1000)$ 头牛要去参加一场在编号为 $x(\le x\le N)$ 的牛的农场举行的派对。有 $M(1\le M\le 100000)$ 条有向道路，每条路长 T i (1≤ T i ≤100) T_i(1\\le T_i\\le100) Ti​(1≤Ti​≤100)。
每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这 $N$ 头牛的最短路径（一个来回）中最长的一条的长度。 特别提醒：可能有权值不同的重边。
输入格式
第 $1$ 行：$3$ 个空格分开的整数 ；
第 $2\dots M+1$ 行：$3$ 个空格分开的整数 A i , B i , T i A_i,B_i,T_i Ai​,Bi​,Ti​，表示有一条从 A i A_i Ai​ 到 B i B_i Bi​ 的路，长度为 T i T_i Ti​。
输出格式
一行一个数，表示最长最短路的长度。

回家的最短路很简单，以 $x$ 为起点跑 Dijkstra 就行了，但是图是有向图，去的路和回来的路不一样，难道以每个点为起点跑一遍 Dijkstra？其实可以用另一个邻接表存反向边，然后去的路就变成了回来的路，以 $x$ 为起点对反图跑一遍最短路就行了。

#include#define int long long//#define lc p<<1//#define rc p<<1|1//#define lowbit(x) x&-x#define psp putchar(\' \')#define endl putchar(\'\\n\')using namespace std;const int N=1e6+5;const int M=1e3+5;int read(){int x=0,f=1;char c=getchar();while(c<\'0\'||c>\'9\'){if(c==\'-\')f=-1;c=getchar();}while(c>=\'0\'&&c<=\'9\')x=(x<<3)+(x<<1)+c-\'0\',c=getchar();return x*f;}void print(int x){if(x<0)putchar(\'-\'),x=-x;if(x<10){putchar(x+\'0\');return;}print(x/10);putchar(x%10+\'0\');}void putstr(string s){for(char v:s)putchar(v);}int n,m,k;int T;struct node{int to,dis;friend bool operator<(node a,node b){return a.dis>b.dis;}};vector<node>a[N];vector<node>b[N];int dis[N];int dis2[N];int vis[N];priority_queue<node>q;signed main(){//ios::sync_with_stdio(0);n=read(),m=read(),k=read();while(m--){int u=read(),v=read(),w=read();a[u].push_back(node{v,w});b[v].push_back(node{u,w});}for(int i=1;i<=n;i++)dis[i]=1e18;dis[k]=0;q.push(node{k,0});while(!q.empty()){int x=q.top().to;q.pop();if(vis[x])continue;vis[x]=1;for(int i=0;i<a[x].size();i++){int y=a[x][i].to;int z=a[x][i].dis;dis[y]=min(dis[y],dis[x]+z);if(!vis[y])q.push(node{y,dis[y]});}}for(int i=1;i<=n;i++)dis2[i]=1e18,vis[i]=0;dis2[k]=0;q.push(node{k,0});while(!q.empty()){int x=q.top().to;q.pop();if(vis[x])continue;vis[x]=1;for(int i=0;i<b[x].size();i++){int y=b[x][i].to;int z=b[x][i].dis;dis2[y]=min(dis2[y],dis2[x]+z);if(!vis[y])q.push(node{y,dis2[y]});}}int mx=0;for(int i=1;i<=n;i++)mx=max(mx,dis[i]+dis2[i]);print(mx);}