当前位置: 首页 > news >正文

正反向建图——kuangbin最短路专题总结(2)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_37087993/article/details/103291335

POJ 3268 Silver Cow Party
POJ 1511 Invitation Cards

两道题都是有向图,求源点到各点,再从各店回到源点的最短路

一开始有点纳闷怎么求回来的最短路,后来想到只要将图的边全部反向,再求一边源点的最短路就可以了

还有一点注意的:复杂度低的图论题,数据量和数据值一般会大,所以不用快读快输的话也尽量用scanf和printf而不是cin和cout

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int maxm = 1000005;
const ll INF = 1e12;
int n,m,tot;
ll ans;
int head[2][maxm],vis[maxm];
ll d[maxm];
struct edge
{
    int u,v,w,nxt;
}es[2][maxm];
void add(int k,int u,int v,int w)
{
    es[k][tot].u=u;
    es[k][tot].v=v;
    es[k][tot].w=w;
    es[k][tot].nxt = head[k][u];
    head[k][u]=tot;
}
void spfa(int k)
{
    queue<int>q;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        d[i] = INF;
    }
    d[1] = 0;
    q.push(1);
    vis[1] = 1;
    while(!q.empty())
    {
        int u =q.front();q.pop();
        vis[u] = 0;
        for(int i=head[k][u];i!=-1;i=es[k][i].nxt)
        {
            int v = es[k][i].v,w=es[k][i].w;
            if(d[v]>d[u]+w)
            {
                d[v] = d[u]+w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    for(int i=2;i<=n;i++) ans+=d[i];
}
int main ()
{
    int t,u,v,w;
    scanf("%d",&t);
    while(t--)
    {
        tot = 0;
        ans = 0;
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(0,u,v,w);
            add(1,v,u,w);
            tot++;
        }
        spfa(0);
        spfa(1);
        printf("%lld\n",ans);
    }
    return 0;
}

相关文章:

  • 别再瞎猜了!“携号转网”后谁是赢家?看完这篇便知晓...
  • 安卓ssss定位
  • SpringBoot 导出 Excel
  • 剑指offer第14题:链表中倒数第k个结点
  • res下raw和assets的区别
  • CodeBlocks运行程序时弹出360等杀毒软件木马拦截警告提醒
  • 金鸡百花电影节星光熠熠,成龙走红毯和机器人过招
  • roscore和conda都打不开
  • static和this关键字
  • 条款10:令operator=返回一个reference to *this——82
  • PHP 注释规范
  • namenode: Unknown command
  • git 命令收集
  • android.view.InflateException: Binary XML file line #
  • HDU 1000.A + B Problem:~scanf("%d%d",&a,&b)表示什么意思 输入字母字符为什么会进入死循环
  • Docker Images: 构建单机版 Spark 镜像,解决第三方 Jar 包的依赖问题
  • mybatis缓存
  • 夜光带你走进C# 游戏开发等(八十四)擅长的领域
  • 阅读笔记(TIP2019)Subjective and Objective Quality Assessment of Stitched Images for Virtual Reality
  • 国标GB/T28181协议下EasyGBS互联网无插件视频播放器起播慢或延迟高问题解决方案