P1342 请柬
题目描述
在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。
这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
比较简单的一到最短路题目，对于返回，建反向边求最短路即可
#include<cstdio> #include<queue> #include<cstring> #define N 2000005 #define inf 0x7fffffff #define LL long long using namespace std; int tot,n,m,head1[N],d[N],vis[N],head2[N],tpt; LL ans; struct node{ int to,next,dis; }; node e1[N],e2[N]; void add(int u,int v,int w,int tp){ if(tp==1){e1[++tot].to=v;e1[tot].next=head1[u];head1[u]=tot;e1[tot].dis=w;} else {e2[++tpt].to=v;e2[tpt].next=head2[u];head2[u]=tpt;e2[tpt].dis=w;} } inline void spfa(int st,int tp){ for(int i=1;i<=n;i++) d[i]=inf; memset(vis,0,sizeof(vis)); d[st]=0;vis[st]=1;queue<int>q; q.push(st); if(tp==1) while(!q.empty()){ int x=q.front();q.pop();vis[x]=0; for(int i=head1[x];i;i=e1[i].next){ int to=e1[i].to,w=e1[i].dis; if(d[x]+w<d[to]){ d[to]=d[x]+w; if(!vis[to]){ q.push(to);vis[to]=1; } } } } else while(!q.empty()){ int x=q.front();q.pop();vis[x]=0; for(int i=head2[x];i;i=e2[i].next){ int to=e2[i].to,w=e2[i].dis; if(d[x]+w<d[to]){ d[to]=d[x]+w; if(!vis[to]){ q.push(to);vis[to]=1; } } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w,1); add(v,u,w,2); } spfa(1,1); for(int i=1;i<=n;i++){ ans+=d[i]; } spfa(1,2); for(int i=1;i<=n;++i){ ans+=d[i]; } printf("%lld",ans); return 0; }
// luogu-judger-enable-o2 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <stack> #include <queue> #define LL long long using namespace std; #define LL long long LL n,m,s,ans; typedef pair<LL,int> pii; struct ahah{ int nxt,to,dis; }edge1[1000010],edge2[1000006]; int head1[1000010],tot1,head2[1000006],tot2; void add(int x,int y,int z,int flag) { if(flag==1)edge1[++tot1].nxt=head1[x],edge1[tot1].to=y,edge1[tot1].dis=z,head1[x]=tot1; else edge2[++tot2].nxt=head2[x],edge2[tot2].to=y,edge2[tot2].dis=z,head2[x]=tot2; } priority_queue <pii,vector<pii>,greater<pii> >Q; bool vis[1000010]; LL d[1000010]; void dijkstra1(int s) { for(int i=1;i<=n;i++)d[i]=1e15; Q.push(make_pair(0,s)); d[s]=0; while(!Q.empty()) { while(!Q.empty()&&vis[Q.top().second])Q.pop(); if(Q.empty())return ; int temp=Q.top().second; d[temp]=Q.top().first; vis[temp]=1;Q.pop(); for(int i=head1[temp];i;i=edge1[i].nxt) { if(!vis[edge1[i].to])Q.push(make_pair(d[temp]+edge1[i].dis,edge1[i].to)); } } return ; } void dijkstra2(int s) { for(int i=1;i<=n;i++)d[i]=1e15; Q.push(make_pair(0,s)); d[s]=0; while(!Q.empty()) { while(!Q.empty()&&vis[Q.top().second])Q.pop(); if(Q.empty())return ; int temp=Q.top().second; d[temp]=Q.top().first; vis[temp]=1;Q.pop(); for(int i=head2[temp];i;i=edge2[i].nxt) { if(!vis[edge2[i].to])Q.push(make_pair(d[temp]+edge2[i].dis,edge2[i].to)); } } return ; } main() { int x,y,z; scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z,1);add(y,x,z,2); } dijkstra1(1); for(int i=2;i<=n;i++)ans+=d[i]; memset(vis,0,sizeof(vis)); dijkstra2(1); for(int i=2;i<=n;i++)ans+=d[i]; printf("%lld",ans); }