luoguP1629 邮递员送信 https://www.luogu.org/problemnew/show/P1629
是该好好巩固一下 QAQ
刷水题使我快乐
论两信竞学生如何讨论一道黄题纠结半个小时
正反各跑一遍 spfa 用 1 次 SPFA 找各个点到点 1 的最短路, 然后开一个反向图, 再用 SPFA 搜一下点 1 到反向图各个点的最短路, 反向图中点 1 到各个点的最短路就是普通图中各个点到点 1 的最短路
- #include<bits/stdc++.h>
- using namespace std;
- const int N=1000+5,inf=1e9;
- int n,m,ans=0;
- inline int rd()
- {
- int x=0,w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- return w?-x:x;
- }
- int head[N],head1[N],cnt=0,cnt1=0;
- struct edge
- {
- int v,nxt,w;
- }e[N*100],e1[N*100];
- void add(int u,int v,int w)
- {
- e[++cnt].v=v;
- e[cnt].w=w;
- e[cnt].nxt=head[u];
- head[u]=cnt;
- }
- void add1(int u,int v,int w)
- {
- e1[++cnt1].v=v;
- e1[cnt1].w=w;
- e1[cnt1].nxt=head1[u];
- head1[u]=cnt1;
- }
- int vis[N],dis[N],dis1[N];
- void spfa()
- {
- memset(vis,0,sizeof(vis));
- for(int i=0;i<=n;i++) dis[i]=inf;
- deque<int> q;
- q.push_back(1);
- vis[1]=1,dis[1]=0;
- while(!q.empty())
- {
- int u=q.front();
- q.pop_front();vis[u]=0;
- for(int i=head[u];i;i=e[i].nxt)
- {
- int v=e[i].v,w=e[i].w;
- if(dis[v]>dis[u]+w)
- {
- dis[v]=dis[u]+w;
- if(!vis[v])
- {
- if(!q.empty()&&dis[v]<=dis[q.front()]) q.push_front(v);
- else q.push_back(v);
- vis[v]=1;
- }
- }
- }
- }
- }
- void spfa1()
- {
- memset(vis,0,sizeof(vis));
- for(int i=0;i<=n;i++) dis1[i]=inf;
- deque<int> q1;
- q1.push_back(1);
- vis[1]=1,dis1[1]=0;
- while(!q1.empty())
- {
- int u=q1.front();
- q1.pop_front();vis[u]=0;
- for(int i=head1[u];i;i=e1[i].nxt)
- {
- int v=e1[i].v,w=e1[i].w;
- if(dis1[v]>dis1[u]+w)
- {
- dis1[v]=dis1[u]+w;
- if(!vis[v])
- {
- if(!q1.empty()&&dis1[v]<=dis1[q1.front()])
- q1.push_front(v);
- else
- q1.push_back(v);
- vis[v]=1;
- }
- }
- }
- }
- }
- int main()
- {
- memset(head,0,sizeof(head));
- memset(head1,0,sizeof(head1));
- n=rd(),m=rd();
- for(int i=1;i<=m;i++)
- {
- int u=rd(),v=rd(),w=rd();
- add(u,v,w);add1(v,u,w);
- }
- spfa();spfa1();
- for(int i=1;i<=n;i++)
- ans+=dis[i]+dis1[i];
- printf("%d",ans);
- }
100 昏 spfa
还有一个完全差不多一样的题: 华山论剑 http://10.37.2.111/problem.php?id=1065 但是求的 最短路径 (一个来回) 中最长的一条的长度
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1010;
- const int maxm=100010;
- int n,m,s,cnt=0,cnt1=0;
- int head[maxn],head1[maxn],dis[maxn],vis[maxn],dis1[maxn];
- struct edge
- {
- int u,w,v,next;
- }e[maxm],e1[maxm];
- void add(int u,int v,int w)
- {
- cnt++;
- e[cnt].u=u;
- e[cnt].v=v;
- e[cnt].w=w;
- e[cnt].next=head[u];
- head[u]=cnt;
- }
- void add1(int u,int v,int w)
- {
- cnt1++;
- e1[cnt1].u=u;
- e1[cnt1].v=v;
- e1[cnt1].w=w;
- e1[cnt1].next=head1[u];
- head1[u]=cnt1;
- }
- queue<int> q;
- void spfa()
- {
- q.push(s);
- dis[s]=0;vis[s]=1;
- while(!q.empty())
- {
- int u=q.front();
- q.pop();vis[u]=0;
- for(int i=head[u];i!=-1;i=e[i].next)
- {
- int v=e[i].v,w=e[i].w;
- if(dis[v]>dis[u]+w)
- {
- dis[v]=dis[u]+w;
- if(vis[v]==0)
- {
- q.push(v);
- vis[v]=1;
- }
- }
- }
- }
- }
- void spfa1()
- {
- q.push(s);
- dis1[s]=0;vis[s]=1;
- while(!q.empty())
- {
- int u=q.front();
- q.pop();vis[u]=0;
- for(int i=head1[u];i!=-1;i=e1[i].next)
- {
- int v=e1[i].v,w=e1[i].w;
- if(dis1[v]>dis1[u]+w)
- {
- dis1[v]=dis1[u]+w;
- if(vis[v]==0)
- {
- q.push(v);
- vis[v]=1;
- }
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d%d",&n,&m,&s);
- memset(head,-1,sizeof(head));
- memset(head1,-1,sizeof(head1));
- memset(vis,0,sizeof(vis));
- memset(dis,0x3f3f3f3f,sizeof(dis));
- memset(dis1,0x3f3f3f3f,sizeof(dis1));
- for(int i=1;i<=m;i++)
- {
- int u,w,v;
- scanf("%d%d%d",&u,&v,&w);
- add(u,v,w);
- add1(v,u,w);
- }
- spfa();
- memset(vis,0,sizeof(vis));
- spfa1();
- int ans=-1;
- for(int i=1;i<=n;i++)
- ans=max(dis[i]+dis1[i],ans);
- printf("%d",ans);
- return 0;
- }
100 昏 华山论剑
来源: http://www.bubuko.com/infodetail-2957551.html