题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1535
题意
给定单向图,从1点走到其他任意一点,再返回n,直到所有点走完,求最短路。
思路
图是单向的,从1点跑最短路可以得到1到其他点的最短距离。反向建图从1点跑最短路可以得到其他点到1点的最短距离,边要先保存起来,正向跑完后销毁,建反向再跑一次。同时建正向和反向超内存。。
#include<cstdio>
#include<queue>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<string>
#include<set>
#include<stack>
#include<algorithm>
#define cle(a) memset(a,0,sizeof(a))
#define inf(a) memset(a,0x3f,sizeof(a))
#define ll long long
#define Rep(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
#define INF2 9223372036854775807ll
const int INF = ( ) + ;
const ll maxn = ;
struct edge
{
int v,w,next;
}e[maxn];
struct Edge
{
int u,v,w;
};
vector<Edge> E;
int vis[maxn],d[maxn],head[maxn];
int tot;
int SPFA(int s,int n)
{
queue<int> q;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)d[i]=INF;
d[s]=;
q.push(s);
vis[s]=;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=;
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].v;
int w=e[i].w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
}
int ret=;
for(int i=;i<=n;i++)ret+=d[i];
return ret;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
E.clear();
tot=;
memset(head,-,sizeof(head));
for(int i=;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
E.push_back(Edge{u,v,w});
}
for(int i=,L=E.size();i<L;i++)
{
int u=E[i].u,v=E[i].v,w=E[i].w;
e[tot].v=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot++;
}
int a1=SPFA(,n);
tot=;
memset(head,-,sizeof(head));
for(int i=,L=E.size();i<L;i++)
{
int u=E[i].u,v=E[i].v,w=E[i].w;
e[tot].v=u;
e[tot].w=w;
e[tot].next=head[v];
head[v]=tot++;
}
int a2=SPFA(,n);
printf("%d\n",a1+a2);
}
}