A+B最短路解法

思路

这题实际上就是求两条连接 $1、2$ 和 $2、3$ 的边的从 $1$ 到 $3$ 的最短路。

代码

#include<bits/stdc++.h>
using namespace std;
int head[6500005],cnt,dis[6500005],n=3,m=2,x,y,z;
bool vis[6500005];
struct Edge
{
	int v,nxt,w;
}e[6200005];
void add(int u,int v,int w)
{
	cnt++;
	e[cnt].v=v;
	e[cnt].nxt=head[u];
	e[cnt].w=w;
	head[u]=cnt;
}
void dijkstra(int s)
{
	for(int i=1;i<=n;i++)dis[i]=INT_MAX;
	dis[s]=0;
	for(int i=1;i<n;i++)
	{
		int u,minn=INT_MAX;
		for(int j=1;j<=n;j++)
		{
			if(vis[j]==0&&dis[j]<minn)
			{
				minn=dis[j];
				u=j;
			}
		}
		vis[u]=1;
		for(int j=head[u];j;j=e[j].nxt)
		{
			int v=e[j].v,w=e[j].w;
			if(vis[v]==0&&dis[v]>dis[u]+w)dis[v]=dis[u]+w;
		}
	}
}
int main()
{
    int s,t;
    cin>>s>>t;
    add(1,2,s);
    add(2,3,t);
    dijkstra(1);
    cout<<dis[3];
	return 0;
}