洛谷月赛

第一题 很水
第二题 由题意得路径一定没有环；
跑三遍dij求出三个给定点到任意点的距离，然后枚举分叉点;

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e6+7;
struct node{
	int id;
}s[N];
struct edge{
	int v,nxt;
}e[N<<2];
int n,m,a,b,c,cnt,st,ed1,ed2;
long long ans=1e15;
int head[N],w[N],vis[N],pre[N];
long long dis[3][N];
void add_edge(int u,int v){
	e[++cnt]=(edge){v,head[u]};
	head[u]=cnt;
}
/*
void spfa(){
	memset(dis,0x7f,sizeof(dis));
	queue<int> q;
	q.push(st);
	vis[st]=1;
	dis[st]=w[st];
	while(q.size()){
		int now=q.front();
		q.pop();
		vis[now]=0;
		for(int i=head[now];i;i=e[i].nxt){
			int to=e[i].v;
			if(dis[to]>dis[now]+w[to]){
				dis[to]=dis[now]+w[to];
				pre[to]=now;
				if(!vis[to]){
					q.push(to);
					vis[to]=1;
				}
			}
		}
	}
}
*/
void dij(int tt,int x){
	priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >q;
	memset(vis,0,sizeof(vis));
	q.push(make_pair(w[x],x));
//	vis[x]=1;
	dis[tt][x]=w[x];
	while(q.size()){
		int now=q.top().second;
		q.pop();
		if(vis[now]) continue;
		vis[now]=1;
//		cout<<"-->"<<now<<"
";
		for(int i=head[now];i;i=e[i].nxt){
			int to=e[i].v;
//			cout<<dis[tt][to]<<"
";
			if(dis[tt][now]+w[to]<dis[tt][to]){
//				cout<<now<<" "<<to<<"
";
//				cout<<dis[tt][now]+w[to]<<"
";
				dis[tt][to]=dis[tt][now]+w[to];
				q.push(make_pair(dis[tt][to],to));
			}
		}
	}
}
int main(){
	scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
	st=a;
	ed1=n*(n-1)+b;
	ed2=n*(n-1)+c; 
	for(int i=1;i<=n*m;i++){
		scanf("%d",&w[i]);	
		s[i].id=i;
	}
	for(int i=1;i<=n*m;i++){
		int shang=s[i].id-n;
		int xia=s[i].id+n;
		int zuo=s[i].id-1;
		int you=s[i].id+1;
		if(shang>=1&&shang<=n*m) add_edge(s[i].id,shang);
		if(xia>=1&&xia<=n*m) add_edge(s[i].id,xia);
		if(zuo>=1&&zuo<=n*m&&zuo%n!=0) add_edge(s[i].id,zuo);
		if(you>=1&&you<=n*m&&you%n!=1) add_edge(s[i].id,you);
	}
	memset(dis,0x7f,sizeof(dis));
//	cout<<ans;
//	cout<<dis[1][1];
	dij(0,st);
	dij(1,ed1);
	dij(2,ed2);
//	cout<<dis[ed1];
//	for(int i=1;i<=n*m;i++){
//		cout<<dis[0][i]<<" "<<dis[1][i]<<" "<<dis[2][i]<<"
"; 
//	}
	for(int i=1;i<=n*m;i++){
//		cout<<dis[1][i]<<" "<<dis[2][i]<<" "<<dis[3][i]<<"
";
		ans=min(dis[0][i]+dis[1][i]+dis[2][i]-2*w[i],ans);
	}
	cout<<ans;
}