図論:マルチペア単一最短パス

最短ルートを解く時、単対多の最短経路、多対多はすでに既成のアルゴリズムがあって、それではどのように多対単を求めますか?簡単で、逆方向に図を作ってspfa、ford、dijkstraなどのアルゴリズムを使うだけでいいです.次の例題はちょうど単対多と多対単の応用です.タイトルリンク:ここをクリック

#include
#include
#include
#include
#include
#include
#define maxd 1000+5
#define maxm 100000+5
using namespace std;
struct edge{
	int to,next,w;
}kkk[maxm],fedge[maxm];
int head[maxd],dis[maxd],cnt=0,fcnt=0,fhead[maxd],fdis[maxd];
bool visit[maxd],fvisit[maxd];
void addedge(int u,int v,int w){
	cnt++;
	kkk[cnt].to=v;
	kkk[cnt].w=w;
	kkk[cnt].next=head[u];
	head[u]=cnt;
	fedge[cnt].to=u;
	fedge[cnt].w=w;
	fedge[cnt].next=fhead[v];
	fhead[v]=cnt;
}//        
struct node{
	int dis;//   
	int pos;//   
	bool operator <( const node &x )const{
        return x.dis < dis;
    }
};
priority_queue<node>q;//      
priority_queue<node>fq; 
int u,v,w;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) dis[i]=fdis[i]=2147483647;//dis    
	memset(visit,0,sizeof(visit));
	memset(fvisit,0,sizeof(fvisit));
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
	}//   
	dis[1]=0;
	q.push((node){0,1});//   
	while(!q.empty()){
		node p=q.top();
		q.pop();
		int x=p.pos;
		if(visit[x]) continue; 
		visit[x]=1;
		for(int i=head[x];i;i=kkk[i].next){
			if(dis[kkk[i].to]>dis[x]+kkk[i].w){
				dis[kkk[i].to]=dis[x]+kkk[i].w;
				if( !visit[kkk[i].to] ){
                    q.push( ( node ){dis[kkk[i].to], kkk[i].to} );
                }
			}
		}
	}
	int ans=0;
	fdis[1]=0;
	fq.push((node){0,1});//   
	while(!fq.empty()){
		node p=fq.top();
		fq.pop();
		int x=p.pos;
		if(fvisit[x]) continue; 
		fvisit[x]=1;
		for(int i=fhead[x];i;i=fedge[i].next){
			if(fdis[fedge[i].to]>fdis[x]+fedge[i].w){
				fdis[fedge[i].to]=fdis[x]+fedge[i].w;
				if( !fvisit[fedge[i].to] ){
                    fq.push( ( node ){fdis[fedge[i].to],fedge[i].to} );
                }
			}
		}
	}
	for(int i=2;i<=n;i++) {
	 	ans=ans+dis[i]+fdis[i];
	}
	cout<<ans;
    return 0;
}