题意：
给定一个有向图，求从源点到其他各点的往返最短路径和。且这个图有一个性质：任何一个环都会经过源点。
图中的节点个数范围：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 0x3f3f3f3f
typedef 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 0x3f3f3f3f
typedef 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);
}
}