本文主要是介绍POJ - 1511 Invitation Cards 反向建图最短路——快读的力量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
POJ-1511
题意
给定n节点m条单向路，求节点1到所有节点再返回的总花费。
思路
基本同 POJ - 3268 。数据范围开到1e6，锁定堆优化dij了。双向建图，跑两遍dij，求和完事。
注意两点，1是开long long，我没试int，但看这数据范围估计多半会wa。2是数据量太大要注意读入,关流cin直接T(天晓得不关流要跑几年)，scanf跑了2100ms，换成快读只跑了1500ms，快读这东西是真顶啊。
代码
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;typedef pair <int,int> P;const int maxn=1000005;const int maxe=1000005;const ll inf=0x3f3f3f3f3f3f3f3f;int head[maxn],head2[maxn];struct Edge{int to;int next;ll w;} edge[maxe],edge2[maxe];int cnt;int n,m;ll dis[maxn];//´æ·Å¾àÀë ll dis2[maxn];ll u,v,w; template <typename T>void read(T &x){x=0;char ch=getchar();ll f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}void init(){cnt=0;for(int i=0;i<=n;i++){head[i]=-1;head2[i]=-1;dis[i]=inf;dis2[i]=inf;}return ;}inline void add(int u,int v,ll w){edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].w=w;head[u]=cnt;edge2[cnt].next=head2[v];edge2[cnt].to=u;edge2[cnt].w=w;head2[v]=cnt;cnt++;}void dij(int start){priority_queue<P,vector<P>,greater<P> > q;dis[start]=0;q.push(P(0,start));while(!q.empty()){P p=q.top(); q.pop();int v=p.second;if(dis[v]<p.first) continue;for(int i=head[v];~i;i=edge[i].next){int tmp=edge[i].to;if(dis[tmp]>dis[v]+edge[i].w){dis[tmp]=dis[v]+edge[i].w;q.push(P(dis[tmp],tmp));}}}return ;}void dij2(int start){priority_queue<P,vector<P>,greater<P> > q;dis2[start]=0;q.push(P(0,start));while(!q.empty()){P p=q.top(); q.pop();int v=p.second;if(dis2[v]<p.first) continue;for(int i=head2[v];~i;i=edge2[i].next){int tmp=edge2[i].to;if(dis2[tmp]>dis2[v]+edge2[i].w){dis2[tmp]=dis2[v]+edge2[i].w;q.push(P(dis2[tmp],tmp));}}}return ;}int main(){int tn;//scanf("%d",&tn);read(tn);while(tn--){read(n),read(m);scanf("%d%d",&n,&m);init();while(m--){//scanf("%lld%lld%lld",&u,&v,&w);read(u),read(v),read(w);add(u,v,w);}dij(1),dij2(1);ll ans=0;for(int i=1;i<=n;i++)ans+=dis[i]+dis2[i];printf("%lld\n",ans);}return 0;}这篇关于POJ - 1511 Invitation Cards 反向建图最短路——快读的力量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
