题意：

给定一个有向图，求从源点到其他各点的往返最短路径和。且这个图有一个性质：任何一个环都会经过源点。

图中的节点个数范围：0～100w;

分析：

   我们先可以利用Dijkstra算法求解从源点到其余各点的最短距离，这样工作就完成了一半了。

那么如何求解从各点到源点的最短路呢？

   1. 我们可以循环n-1次，每次计算点i到其余各点的最短路，从中取出i到源点的最短路，这样我们就可以其余各点到源点的最短路。

       显然上述方法中存在大量冗余，显然针对题目的取值范围:0~100w，必定会超时的。如果你不信，可以试试。  

       按照上诉方法实践，超时的代码：

#include<cstdio>#include<string.h>#include<iostream>#include<vector>#include<queue>using namespace std;#define maxn 1000000#define inf 0x3f3f3f3ftypedef pair<int,int> P;struct edge{	int t;	int c;	edge(){	t=0,c=0;}	edge(int tt,int cc){		t=tt,c=cc;	}};int dist[maxn];vector<edge> map[maxn];void dijkstra(int s,int n){	priority_queue<P,vector<P>,greater<P> > Q;	for(int i=1;i<=n;i++)		dist[i]=inf;	dist[s]=0;	bool visited[maxn];	memset(visited ,0,sizeof(visited));	Q.push(P(0,s));	while(!Q.empty()){		int v=Q.top().second;		Q.pop();		if(visited[v])  continue;		visited[v]=true;		for(int i=0;i<map[v].size();i++){			edge e=map[v][i];			if(dist[e.t]>dist[v]+e.c){				dist[e.t]=dist[v]+e.c;				Q.push(P(dist[e.t],e.t));			}		}	}}void init(int n){	for(int i=0;i<=n;i++){		map[i].clear();	}}int main(){	//freopen("in.txt","r",stdin);	int cases;	scanf("%d",&cases);	for(int t=1;t<=cases;t++){		int n,m;		scanf("%d %d",&n,&m);		init(n);		while(m--){			int a,b,c;			scanf("%d %d %d",&a,&b,&c);			map[a].push_back(edge(b,c));		}		dijkstra(1,n);		int sum=0;		for(int i=1;i<=n;i++)			sum+=dist[i];		for(int i=2;i<=n;i++){			dijkstra(i,n);			sum+=dist[1];		}		printf("%d\n",sum);	}}

2.经过别人题解指点，发现一个很好的方法。

首先，我们需要构造原图的反图。

原图为有向图，反图为建立在原图的基础之上，原图的边的源点为反图的终点，原图的边的终点为反图的源点。

总之，把原图的边的方向全部反转，就构成了反图。

在构建完反图后，我们再来对反图应用Dijkstra算法，源点为1.

接着，我们获得了从源点到其余各点的最短距离，注意我们的图是原图的反图，所以：

我们获得的其实是其余各点到源点的最短距离。

 

3.邻接表还是二维矩阵？

我们还需注意一个重要的问题：如何存储边信息？

按照题目中的数据范围0-100w，我们是无法开辟那么大的二维矩阵的，所以我们必须利用邻接表存储。

在这里我们使用vector实现。

源代码：

#include<cstdio>#include<string.h>#include<iostream>#include<vector>#include<queue>using namespace std;#define maxn 1000001#define inf 0x3f3f3f3ftypedef pair<int,int> P;struct edge{	int f;	int t;	int c;	edge(){	f=0,t=0,c=0;}	edge(int ff,int tt,int cc){		f=ff,t=tt,c=cc;	}};int dist[maxn];vector<edge> map[maxn];edge edges[maxn];void dijkstra(int s,int n){	priority_queue<P,vector<P>,greater<P> > Q;	for(int i=1;i<=n;i++)		dist[i]=inf;	dist[s]=0;	bool visited[maxn];	memset(visited ,0,sizeof(visited));	Q.push(P(0,s));	while(!Q.empty()){		int v=Q.top().second;		Q.pop();		if(visited[v])  continue;		visited[v]=true;		for(int i=0;i<map[v].size();i++){			edge e=map[v][i];			if(dist[e.t]>dist[v]+e.c){				dist[e.t]=dist[v]+e.c;				Q.push(P(dist[e.t],e.t));			}		}	}}void init(int n){	for(int i=0;i<=n;i++){		map[i].clear();	}}int main(){	//freopen("in.txt","r",stdin);	int cases;	scanf("%d",&cases);	for(int t=1;t<=cases;t++){		int n,m;		scanf("%d %d",&n,&m);		init(n);		for(int i=1;i<=m;i++){			int a,b,c;			scanf("%d %d %d",&a,&b,&c);			edges[i]=edge(a,b,c);			map[a].push_back(edge(a,b,c));		}		dijkstra(1,n);		long long int sum=0;		for(int i=1;i<=n;i++)			sum+=dist[i];		init(n);		for(int i=1;i<=m;i++){			edge tmp=edges[i];			map[tmp.t].push_back(edge(tmp.t,tmp.f,tmp.c));		}		dijkstra(1,n);		for(int i=1;i<=n;i++)			sum+=dist[i];		printf("%lld\n",sum);	}}

POJ - 1511 Invitation Cards（Dijkstra变形题）