【每日一题】9月11日题目精讲

道路和航线

https://ac.nowcoder.com/acm/problem/50381

SPFA+SLF优化,直接朴素的SPFA会卡掉。
当然用SPFA+LLL+SLF应该也是可以的,但是我不是很会LLL,但是一个SLF优化就可以过了。
题目当中说:双向边是非负的而单向边没有环,所以,我们可以先把有双向边链接的若干个点缩成一个点,然后点之间连上单向边之后这张图是一个有向无环图,所以跑广搜就可以了。而连通块内部因为边非负,所以可以dijkstra。

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
///////////////////////////////////////////////////////////
int n,m,w;
int T, R, P, S;
struct Edge
{
    int v, w, next;
}edge[N];
int head[N], dis[N],  t;
bool vis[N];
void init(){
    memset(dis, 0x3f, sizeof dis);
}
inline void Add_edge(int u, int v, int w)
{
    edge[++t].next= head[u];
    head[u] = t;
    edge[t].v = v;
    edge[t].w = w;
}
inline void SPFA()
{
    deque <int> q;
    q.push_front(S);
    dis[S] = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop_front();
        vis[now] = 0;
        for (int i = head[now]; i; i = edge[i].next) {
            if (dis[edge[i].v] <= edge[i].w + dis[now]) continue;
            dis[edge[i].v] = edge[i].w + dis[now];
            if (vis[edge[i].v]) continue;
            vis[edge[i].v] = 1;
            if (q.empty() || dis[edge[i].v] <= dis[q.front()]) q.push_front(edge[i].v);
            else q.push_back(edge[i].v);
        }
    }
}
int main()
{
    cin>>T>>R>>P>>S;
     while (R--) {
        int a,b,c;
        cin>>a>>b>>c;
        Add_edge(a, b, c), Add_edge(b, a, c);
    }
    while (P--) {
        int a,b,c;
        cin>>a>>b>>c;
        Add_edge(a, b, c);
    }
    init();
    SPFA();
    for (int i = 1; i <= T; ++i) {
        if (dis[i] == INF) {
            cout<<"NO PATH"<<endl;
        }
        else {
            cout<<dis[i]<<endl;
        }
    }
    return 0;
}
全部评论

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
05-09 13:22
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务