个人空间 - AcWing

Yangchang

关注数

粉丝数

阅读量

226

+关注发消息

离线：5天前

最近来访(0)

活动打卡代码 AcWing 854. Floyd求最短路

Yangchang
6天前

                #include <bits/stdc++.h>
#define cint const int &
#define pii pair<int, int>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 201, maxm = 20001;
struct {
    int nxt, v, w;
} edge[maxm + maxn];
struct {
    int nxt, y;
} qry[maxn * maxn];
int head[maxn], qrys[maxn], cnt, qcnt, n, m, k, x, y, z;
inline void addedge(cint u, cint v, cint w) {
    edge[++cnt] = {head[u], v, w};
    head[u] = cnt;
}
inline void addqry(cint x, cint y) {
    qry[++qcnt] = {qrys[x], y};
    qrys[x] = qcnt;
}
int h[maxn], dis[maxn];
bool vis[maxn];
inline void spfa(cint s, cint n) {
    static queue<int> q;
    memset(h, inf, sizeof(h[0]) * (n + 1));
    memset(vis, 0, n + 1);
    q.push(s); h[s] = 0;
    while (!q.empty()) {
        const int u = q.front();
        q.pop(); vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].nxt) {
            const int v = edge[i].v, w = edge[i].w;
            if (h[v] > h[u] + w) {
                h[v] = h[u] + w;
                if (!vis[v])
                    vis[v] = 1,
                    q.push(v);
            }
        }
    }
}
inline void dijkstra(cint s, cint n) {
    static priority_queue<pii, vector<pii>, greater<pii>> pq;
    memset(dis, inf, sizeof(dis[0]) * (n + 1));
    memset(vis, 0, n + 1);
    pq.push({dis[s] = 0, s});
    int u, du;
    while (!pq.empty()) {
        tie(du, u) = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].nxt) {
            const int v = edge[i].v, w = edge[i].w;
            if (dis[v] > du + w)
                pq.push({dis[v] = du + w, v});
        }
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    //  ifstream ifs(".in");
    //  ofstream ofs(".out");
    //  cin.rdbuf(ifs.rdbuf()),cout.rdbuf(ofs.rdbuf());
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i)
        cin >> x >> y >> z, addedge(x, y, z);
    for (int i = 1; i <= k; ++i)
        cin >> x >> y, addqry(x, y);
    for (int i = 1; i <= n; ++i)
        addedge(0, i, 0);
    spfa(0, n);
    for (int u = 1; u <= n; ++u)
        for (int i = head[u]; i; i = edge[i].nxt)
            edge[i].w += h[u] - h[edge[i].v];
    for (int x = 1; x <= n; ++x) {
        dijkstra(x, n);
        for (int i = qrys[x]; i; i = qry[i].nxt) {
            const int y = qry[i].y;
            if (dis[y] == inf) qry[i].y = inf;
            else qry[i].y = dis[y] - h[x] + h[y];
        }
    }
    for (int i = 1; i <= k; ++i)
        if (qry[i].y == inf) cout << "impossible\n";
        else cout << qry[i].y << '\n';
}

            

题解 AcWing 854. Johnson 算法

Yangchang
6天前

                #include <bits/stdc++.h>
#define cint const int &
#define pii pair<int, int>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 201, maxm = 20001;
struct {
    int nxt, v, w;
} edge[maxm + maxn];
struct {
    int nxt, y;
} qry[maxn * maxn];
int head[maxn], qrys[maxn], cnt, qcnt, n, m, k, x, y, z;
inline void addedge(cint u, cint v, cint w) {
    edge[++cnt] = {head[u], v, w};
    head[u] = cnt;
}
inline void addqry(cint x, cint y) {
    qry[++qcnt] = {qrys[x], y};
    qrys[x] = qcnt;
}
int h[maxn], dis[maxn];
bool vis[maxn];
inline void spfa(cint s, cint n) {
    static queue<int> q;
    memset(h, inf, sizeof(h[0]) * (n + 1));
    memset(vis, 0, n + 1);
    q.push(s); h[s] = 0;
    while (!q.empty()) {
        const int u = q.front();
        q.pop(); vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].nxt) {
            const int v = edge[i].v, w = edge[i].w;
            if (h[v] > h[u] + w) {
                h[v] = h[u] + w;
                if (!vis[v])
                    vis[v] = 1,
                    q.push(v);
            }
        }
    }
}
inline void dijkstra(cint s, cint n) {
    static priority_queue<pii, vector<pii>, greater<pii>> pq;
    memset(dis, inf, sizeof(dis[0]) * (n + 1));
    memset(vis, 0, n + 1);
    pq.push({dis[s] = 0, s});
    int u, du;
    while (!pq.empty()) {
        tie(du, u) = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].nxt) {
            const int v = edge[i].v, w = edge[i].w;
            if (dis[v] > du + w)
                pq.push({dis[v] = du + w, v});
        }
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    //  ifstream ifs(".in");
    //  ofstream ofs(".out");
    //  cin.rdbuf(ifs.rdbuf()),cout.rdbuf(ofs.rdbuf());
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i)
        cin >> x >> y >> z, addedge(x, y, z);
    for (int i = 1; i <= k; ++i)
        cin >> x >> y, addqry(x, y);
    for (int i = 1; i <= n; ++i)
        addedge(0, i, 0);
    spfa(0, n);
    for (int u = 1; u <= n; ++u)
        for (int i = head[u]; i; i = edge[i].nxt)
            edge[i].w += h[u] - h[edge[i].v];
    for (int x = 1; x <= n; ++x) {
        dijkstra(x, n);
        for (int i = qrys[x]; i; i = qry[i].nxt) {
            const int y = qry[i].y;
            if (dis[y] == inf) qry[i].y = inf;
            else qry[i].y = dis[y] - h[x] + h[y];
        }
    }
    for (int i = 1; i <= k; ++i)
        if (qry[i].y == inf) cout << "impossible\n";
        else cout << qry[i].y << '\n';
}

            

活动打卡代码 AcWing 852. spfa判断负环

Yangchang
6天前

                #include<bits/stdc++.h>
#define inf (int)((1u<<31)-1)
using namespace std;
using cint = const int&;
using pii = pair<int,int>;
const int maxm = 5e5+10,maxn = 1e5+10;
//Tip1: Basic 
struct {
    int nxt,v,w;
}edge[maxm];
int head[maxn],ecnt,n,m,s,a,b,c,qcnt[maxn];
bool vis[maxn];
inline void addedge(cint u,cint v,cint w){
    edge[++ecnt] = {head[u],v,w};
    head[u] = ecnt;
}
//Tip2: MinDis
/// Tip2.1 Dijkstra && SPFA
int dis[maxn];
inline void dijkstra(cint s,cint n){
    memset(vis+1,0,n);
    //memset(dis+1,inf,n * sizeof(dis[0]));
    fill(dis+1,dis+n+1,inf);
    static priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push({dis[s] = 0,s});
    while(!pq.empty()){
        const pii tp = pq.top();pq.pop();
        const int u = tp.second, du = tp.first;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w) pq.push({dis[v] = du + w, v}); 
        }
    }
}
inline bool spfa(cint s,cint n){
    memset(vis+1,0,n);
    fill(dis+1,dis+n+1,inf);
    dis[s] = 0;
    static deque<int> q;
    q.push_back(s);

    while(!q.empty()){
        const int u = q.front(),du = dis[u];q.pop_front();
        vis[u] = 0;
        if(++qcnt[u] == n+1) return 1;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w){
                dis[v] = du + w; 
                if(!vis[v]){ if(1 || dis[v] < dis[q.front()]) q.push_back(v);else q.push_front(v);vis[v]=1;}
            }
        }
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>a>>b>>c;
        addedge(a,b,c);

    }
    for(int i = 1;i<=n;++i) addedge(0,i,0);
    if(spfa(0,n)) cout<<"Yes";
    else cout<<"No";
}

            

活动打卡代码 AcWing 851. spfa求最短路

Yangchang
6天前

                #include<bits/stdc++.h>
#define inf (int)((1u<<31)-1)
using namespace std;
using cint = const int&;
using pii = pair<int,int>;
const int maxm = 5e5+10,maxn = 1e5+10;
//Tip1: Basic 
struct {
    int nxt,v,w;
}edge[maxm];
int head[maxn],ecnt,n,m,s,a,b,c;
bool vis[maxn];
inline void addedge(cint u,cint v,cint w){
    edge[++ecnt] = {head[u],v,w};
    head[u] = ecnt;
}
//Tip2: MinDis
/// Tip2.1 Dijkstra && SPFA
int dis[maxn];
inline void dijkstra(cint s,cint n){
    memset(vis+1,0,n);
    //memset(dis+1,inf,n * sizeof(dis[0]));
    fill(dis+1,dis+n+1,inf);
    static priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push({dis[s] = 0,s});
    while(!pq.empty()){
        const pii tp = pq.top();pq.pop();
        const int u = tp.second, du = tp.first;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w) pq.push({dis[v] = du + w, v}); 
        }
    }
}
inline void spfa(cint s,cint n){
    memset(vis+1,0,n);
    fill(dis+1,dis+n+1,inf);
    dis[s] = 0;
    static deque<int> q;
    q.push_back(s);

    while(!q.empty()){
        const int u = q.front(),du = dis[u];q.pop_front();
        vis[u] = 0;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w){
                dis[v] = du + w; 
                if(!vis[v]){ if(1 || dis[v] < dis[q.front()]) q.push_back(v);else q.push_front(v);vis[v]=1;}
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>a>>b>>c;
        addedge(a,b,c);
    }
    spfa(1,n);
    if(dis[n] == inf) cout<<"impossible";
    else cout<<dis[n];
}

            

题解 AcWing 841. 正经后缀数组做法

Yangchang
6天前

                #include<bits/stdc++.h>
#define cint const int&
#define cstr const auto*const
using namespace std;
const int maxn = 1e5 + 1, lim = 30;
int l1, l2, r1, r2, a[maxn], sa[maxn], rk[maxn], tp[maxn << 1], bn[maxn], hzr[maxn], n, m;
char s[maxn];
inline void getsa(cstr s, cint n) {
    int m = max(n, 255);
    memset(bn + 1, 0, sizeof(bn[0]) * m);
    for (int i = 1; i <= n; ++i) ++bn[rk[i] = s[i]];
    for (int i = 2; i <= m; ++i) bn[i] += bn[i - 1];
    for (int i = n; i > 0; --i) sa[bn[rk[i]]--] = i;
    for (int j = 1, cnt = 0; j <= n; j <<= 1, cnt = 0) {
        for (int i = n - j + 1; i <= n; ++i) tp[++cnt] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] - j > 0) tp[++cnt] = sa[i] - j;
        memset(bn + 1, 0, sizeof(bn[0]) * m);
        for (int i = 1; i <= n; ++i) ++bn[rk[i]];
        for (int i = 2; i <= m; ++i) bn[i] += bn[i - 1];
        for (int i = n; i > 0; --i) sa[bn[rk[tp[i]]]--] = tp[i];
        memcpy(tp + 1, rk + 1, sizeof(tp[0]) * n);
        rk[sa[1]] = cnt = 1;
        for (int i = 2; i <= n; ++i)
            rk[sa[i]] = (tp[sa[i]] != tp[sa[i - 1]]) || (tp[sa[i] + j] != tp[sa[i - 1] + j]) ? ++cnt : cnt;
        if ((m = cnt) == n) break;
    }
}
inline void gethzr(cstr s, cint n) {
    for (int i = 1, k = 0; i <= n; ++i) {
        if (rk[i] == 1) continue;
        if (k) --k;
        int j = sa[rk[i] - 1];
        while (j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++k;
        hzr[rk[i]] = k;
    }
}

int minval[lim][maxn];
inline void init(cint n) {
    for (int i = 1; i < lim; ++i)
        for (int j = 1; j + (1 << (i - 1)) <= n; ++j)
        minval[i][j] = min(minval[i - 1][j], minval[i - 1][j + (1 << (i - 1))]);
}
inline int getmin(cint l, cint r) {
    int lg = (8 * sizeof(r - l + 1) - 1) - __builtin_clz(r - l + 1);
    return min(minval[lg][l], minval[lg][r - (1 << lg) + 1]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> s + 1;
    getsa(s, n), gethzr(s, n);
    memcpy(minval[0], hzr, sizeof(hzr[0]) * (n + 1)), init(n);
    while (m--) {
        cin >> l1 >> r1 >> l2 >> r2;
        if (rk[l1] > rk[l2]) swap(l1, l2), swap(r1, r2);
        if (r1 - l1 == r2 - l2 && (l1 == l2 || getmin(rk[l1] + 1, rk[l2]) > r1 - l1))
            cout << "Yes\n";
        else cout << "No\n";
    }
}

            

活动打卡代码 AcWing 853. 有边数限制的最短路

Yangchang
6天前

                #include<bits/stdc++.h>
using namespace std;
const int maxn  = 1e5+10;

struct{int u,v,w;} edge[maxn];
int cnt,n,m,k,dis[maxn],was[maxn];

int main(){
    cin>>n>>m>>k;
    memset(dis+1,0x3f,sizeof(dis[0])*(n));
    dis[1] = 0;
    for(int i = 1;i<=m;++i) cin>>edge[i].u>>edge[i].v>>edge[i].w;

    for(int i = 1;i<=k;++i){
        memcpy(was,dis,sizeof(dis[0])*(n+1));
        for(int j = 1;j<=m;++j)
            dis[edge[j].v] = min(dis[edge[j].v],was[edge[j].u] + edge[j].w);
    }
    if(dis[n] >= 0x0f3f3f3f) cout<<"impossible";
    else cout<<dis[n];
}

            

活动打卡代码 AcWing 850. Dijkstra求最短路 II

Yangchang
6天前

                #include<bits/stdc++.h>
#define inf 2137483647
using namespace std;
using cint = const int&;
using pii = pair<int,int>;
const int maxm = 5e5+1,maxn = 1e5+1;
//Tip1: Basic 
struct {
    int nxt,v,w;
}edge[maxm];
int head[maxn],ecnt,n,m,s,a,b,c;
bool vis[maxn];
inline void addedge(cint u,cint v,cint w){
    edge[++ecnt] = {head[u],v,w};
    head[u] = ecnt;
}
//Tip2: MinDis
/// Tip2.1 Dijkstra && SPFA
int dis[maxn];
inline void dijkstra(cint s,cint n){
    memset(vis+1,0,n);
    memset(dis+1,inf,n * sizeof(dis[0]));
    static priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push({dis[s] = 0,s});
    while(!pq.empty()){
        const pii tp = pq.top();pq.pop();
        const int u = tp.second, du = tp.first;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w) pq.push({dis[v] = du + w, v}); 
        }
    }
}
inline void spfa(cint s,cint n){
    memset(vis+1,0,n);
    memset(dis+1,inf,n * sizeof(dis[0]));
    dis[s] = 0;
    static queue<int> q;
    q.push(s);

    while(!q.empty()){
        const int u = q.front(),du = dis[u];q.pop();
        vis[u] = 0;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w){
                dis[v] = du + w; 
                if(!vis[v]) q.push(v);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>a>>b>>c;
        addedge(a,b,c);
    }
    dijkstra(1,n);
    cout<<(dis[n]==2139062143?-1:dis[n]);
}

            

活动打卡代码 AcWing 849. Dijkstra求最短路 I

Yangchang
6天前

                #include<bits/stdc++.h>
#define inf 2137483647
using namespace std;
using cint = const int&;
using pii = pair<int,int>;
const int maxm = 5e5+1,maxn = 1e5+1;
//Tip1: Basic 
struct {
    int nxt,v,w;
}edge[maxm];
int head[maxn],ecnt,n,m,s,a,b,c;
bool vis[maxn];
inline void addedge(cint u,cint v,cint w){
    edge[++ecnt] = {head[u],v,w};
    head[u] = ecnt;
}
//Tip2: MinDis
/// Tip2.1 Dijkstra && SPFA
int dis[maxn];
inline void dijkstra(cint s,cint n){
    memset(vis+1,0,n);
    memset(dis+1,inf,n * sizeof(dis[0]));
    static priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push({dis[s] = 0,s});
    while(!pq.empty()){
        const pii tp = pq.top();pq.pop();
        const int u = tp.second, du = tp.first;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w) pq.push({dis[v] = du + w, v}); 
        }
    }
}
inline void spfa(cint s,cint n){
    memset(vis+1,0,n);
    memset(dis+1,inf,n * sizeof(dis[0]));
    dis[s] = 0;
    static queue<int> q;
    q.push(s);

    while(!q.empty()){
        const int u = q.front(),du = dis[u];q.pop();
        vis[u] = 0;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w){
                dis[v] = du + w; 
                if(!vis[v]) q.push(v);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>a>>b>>c;
        addedge(a,b,c);
    }
    dijkstra(1,n);
    cout<<(dis[n]==2139062143?-1:dis[n]);
}

            

活动打卡代码 AcWing 848. 有向图的拓扑序列

Yangchang
6天前

                #include<bits/stdc++.h>
#define deb(var) cerr<<"deb: "<< #var <<'='<<(var)<<'\n'
#define mids(l,r) const auto mid = l + r >> 1
#define cint const int&
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f3f
#define ls (x<<1)
#define rs (ls|1)
#define lb(x) x&-x
using namespace std;
const int maxn = 1e5+10;
int ans = inf;
struct{
    int nxt,v;
}edge[maxn << 1];
int head[maxn],cnt,deg[maxn];
inline void addedge(cint a,cint b){
    edge[++cnt] = {head[a],b};
    ++deg[b];
    head[a] = cnt;
}
int u,v,n,m;
int dis[maxn],q[maxn],hd = 1,tl = 1;
inline bool topsort(){
    for(int i = 1;i<=n;++i) if(deg[i] == 0) q[tl++] = i;
    while(hd <= tl){
        const int u = q[hd ++];
        for(int i = head[u];i;i=edge[i].nxt){
            const int v = edge[i].v;
            if(! -- deg[v]) q[tl ++] = v;
        }
    } 
    return tl == n + 1;
}
signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
//  ifstream ifs(".in");
//  ofstream ofs(".out");
//  cin.rdbuf(ifs.rdbuf()),cout.rdbuf(ofs.rdbuf());
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>u>>v;
        addedge(u,v);
    }
    if(topsort())
        for(int i =1;i<=n;++i) cout<<q[i]<<' ';
    else cout<<"-1";
}

            

活动打卡代码 AcWing 847. 图中点的层次

Yangchang
6天前

                #include<bits/stdc++.h>
#define deb(var) cerr<<"deb: "<< #var <<'='<<(var)<<'\n'
#define mids(l,r) const auto mid = l + r >> 1
#define cint const int&
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f3f
#define ls (x<<1)
#define rs (ls|1)
#define lb(x) x&-x
using namespace std;
const int maxn = 1e5+10;
int ans = inf;
struct{
    int nxt,v;
}edge[maxn << 1];
int head[maxn],cnt;
inline void addedge(cint a,cint b){
    edge[++cnt] = {head[a],b};
    head[a] = cnt;
}
int u,v,n,m;
int dis[maxn],q[maxn],hd,tl = 1;
inline void bfs(cint s){
    dis[q[++hd] = s] = 1;

    while(hd <= tl){
        const int u = q[hd++];
        for(int i = head[u];i;i=edge[i].nxt ){
            const int v = edge[i].v;
            if(dis[v])  continue;
            dis[q[++tl] = v] = dis[u] + 1;
        }
    }
}
signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
//  ifstream ifs(".in");
//  ofstream ofs(".out");
//  cin.rdbuf(ifs.rdbuf()),cout.rdbuf(ofs.rdbuf());
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>u>>v;
        addedge(u,v);
    }
    bfs(1);
    cout<<(dis[n]?dis[n]-1:-1);
}

            

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论