|
题目链接
题意：
T组样例
n个顶点，m条单向边
m行 ui，vi，wi.
求源点1到其它点来回最短路
最后输出所有来回最短路相加之和
0<n≤20000,m≤60000,1≤T≤10,0≤ci?≤10^9,1≤ui?,vi,wi?≤n
题解：
单源最短路，且边权值为正数，n数据太大，邻接表存图。
解法1：spfa算法
解法2：堆优化Dijkstra()算法
如何实现堆优化：
- 不同结构体，用pair容器，pair可以放两个元素，相当于一个结构体，然后优先队列自动从小到大排序，排序先按pair中第一个元素排，然后才考虑第二个元素。
- 用结构体，结构体中放一个排序，其实我认为这个比较简单。
注：其实相比迪杰斯特拉算法只是多了一个堆排序，为了更快的找到最小值而已；还有不需要数组标记，根据贪心思想找最小值，不用找就在队列的第一个，而下面的松弛不需要判断是否被标记过，如果v已经被标记，if()肯定不满足的。
代码1：spfa（）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll first[N],nx[N],to[N],s[N],head=1;
ll u[N],v[N],w[N];
ll dis[N],dis1[N],dis2[N],book[N];
void init()
{
head=1;
memset(first,-1,sizeof(first));
}
void add(ll x,ll y,ll z)
{
nx[head]=first[x];
first[x]=head;
to[head]=y;
s[head]=z;
head++;
}
void spfa(ll x)
{
ll i,u,v;
memset(book,0,sizeof(book));
memset(dis,INF,sizeof(dis));
dis[x]=0;
book[x]=1;
queue<ll> q;
q.push(x);
while(!q.empty())
{
u=q.front();
q.pop();
book[u]=0;
for(i=first[u];i!=-1;i=nx[i])
{
v=to[i];
if(dis[v]>dis[u]+s[i])
{
dis[v]=dis[u]+s[i];
if(!book[v])
{
book[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
ll n,m,i;
scanf("%lld %lld",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&u[i],&v[i],&w[i]);
add(u[i],v[i],w[i]);
}
spfa(1);
for(i=1;i<=n;i++) dis1[i]=dis[i];
init();
for(i=1;i<=m;i++)
add(v[i],u[i],w[i]);
spfa(1);
for(i=1;i<=n;i++) dis2[i]=dis[i];
ll ans=0;
for(i=2;i<=n;i++)
ans+=dis1[i]+dis2[i];
printf("%lld\n",ans);
}
return 0;
}
代码2：pair
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pr;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll N=20020;
const ll M=60060;
ll first[N],nx[M],to[M],s[M],head;
ll dis[N],dis1[N],dis2[N];
ll u[M],v[M],w[M];
ll n,m;
void init()
{
head=1;
memset(first,-1,sizeof(first));
}
void add(ll x,ll y,ll z)
{
nx[head]=first[x];
to[head]=y;
s[head]=z;
first[x]=head++;
}
void dui_Dijkstra(ll x)
{
priority_queue<pr,vector<pr>,greater<pr> >Q;
memset(dis,INF,sizeof(dis));
dis[x]=0;
Q.push({dis[x],x});
ll u,v,i;
while(!Q.empty())
{
u=Q.top().second;
Q.pop();
for(i=first[u];i!=-1;i=nx[i])
{
v=to[i];
if(dis[v]>dis[u]+s[i])
{
dis[v]=dis[u]+s[i];
Q.push({dis[v],v});
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
scanf("%lld %lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&u[i],&v[i],&w[i]);
add(u[i],v[i],w[i]);
}
dui_Dijkstra((ll)1);
for(int i=1;i<=n;i++) dis1[i]=dis[i];
init();
for(int i=1;i<=m;i++)
add(v[i],u[i],w[i]);
dui_Dijkstra((ll)1);
for(int i=1;i<=n;i++) dis2[i]=dis[i];
ll ans=0;
for(int i=2;i<=n;i++)
ans+=dis1[i]+dis2[i];
printf("%lld\n",ans);
}
return 0;
}
代码3：结构体
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll N=20020;
const ll M=60060;
ll first[N],nx[M],to[M],s[M],head;
ll dis[N],dis1[N],dis2[N],book[N];
ll u[M],v[M],w[M];
ll n,m;
void init()
{
head=1;
memset(first,-1,sizeof(first));
}
struct Node{
ll p,s;
bool operator <(const Node &W)const
{
return s<W.s;
}
};
void add(ll x,ll y,ll z)
{
nx[head]=first[x];
to[head]=y;
s[head]=z;
first[x]=head++;
}
void dui_Dijkstra(ll x)
{
queue<Node> Q;
struct Node _u,_v;
memset(dis,INF,sizeof(dis));
dis[x]=0;
_v={x,dis[x]};
Q.push(_v);
book[x]=1;
ll u,v,i;
while(!Q.empty())
{
_u=Q.front();
u=_u.p;
Q.pop();
for(i=first[u];i!=-1;i=nx[i])
{
v=to[i];
if(dis[v]>dis[u]+s[i])
{
dis[v]=dis[u]+s[i];
_v={v,dis[v]};
Q.push(_v);
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
scanf("%lld %lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&u[i],&v[i],&w[i]);
add(u[i],v[i],w[i]);
}
dui_Dijkstra((ll)1);
for(int i=1;i<=n;i++) dis1[i]=dis[i];
init();
for(int i=1;i<=m;i++)
add(v[i],u[i],w[i]);
dui_Dijkstra((ll)1);
for(int i=1;i<=n;i++) dis2[i]=dis[i];
ll ans=0;
for(int i=2;i<=n;i++)
ans+=dis1[i]+dis2[i];
printf("%lld\n",ans);
}
return 0;
}
|