杭电多校Age_of_Moyu

Age of Moyu

题解

标程的set+bfs貌似有漏洞。

5 6
1 2 1
2 3 1
3 4 1
4 5 1
1 3 2
1 4 3

这个数据就可以hack掉了。

所以我果断copy了dls队伍的代码。(用边做)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
inline char inputchar()
{
    return getchar();
}
inline void inputnum(int &ret)
{
    char ch = inputchar();
    while(ch < '0' || ch > '9')
        ch = inputchar();
    ret = ch - '0';
    ch = inputchar();
    while(ch >= '0' && ch <= '9')
    {
        ret = ret * 10 + ch - '0';
        ch = inputchar();
    }
}
const int MAXN = 101010, MAXM = 202020;
int n, m;
class Edge
{
public:
    int to, c, next;
}e[MAXM * 2];
int en, head[MAXN];
int dis[MAXM];
deque<int> q;
void insert()
{
    int u, v, c;
//    scanf("%d%d%d", &u, &v, &c);
    inputnum(u);
    inputnum(v);
    inputnum(c);
    e[++en].to = v;
    e[en].c = c;
    e[en].next = head[u];
    head[u] = en;
    e[++en].to = u;
    e[en].c = c;
    e[en].next = head[v];
    head[v] = en;
}
bool solve()
{
    if(scanf("%d%d", &n, &m) != 2)
        return false;
    memset(head, -1, (n + 2) * sizeof(int));
    en = 1;
    for(int i = 1; i <= m; i++)
        insert();
    memset(dis, 1, (m + 2) * sizeof(int));
    for(int i = head[1]; i > 0; i = e[i].next)
        dis[i / 2] = 1, q.push_back(i / 2);
    while(!q.empty())
    {
        int now = q.front();
        q.pop_front();
        for(int i = head[e[now * 2].to]; i > 0; i = e[i].next)
            if(e[i].c == e[now * 2].c)
            {
                if(dis[i / 2] > dis[now])
                    dis[i / 2] = dis[now], q.push_front(i / 2);
            }
            else
            {
                if(dis[i / 2] > dis[now] + 1)
                    dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
            }
        for(int i = head[e[now * 2 + 1].to]; i > 0; i = e[i].next)
            if(e[i].c == e[now * 2 + 1].c)
            {
                if(dis[i / 2] > dis[now])
                    dis[i / 2] = dis[now], q.push_front(i / 2);
            }
            else
            {
                if(dis[i / 2] > dis[now] + 1)
                    dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
            }
    }
    int ans = MAXM;
    for(int i = head[n]; i > 0; i = e[i].next)
        if(ans > dis[i / 2])
            ans = dis[i / 2];
    if(ans == MAXM)
        ans = -1;
    printf("%d\n", ans);
    return true;
}
int main()
{
#ifdef LOCAL
    freopen("a.in","r",stdin);
#endif
    while(solve());
    return 0;
}

时间卡的非常紧。优化了很多终于2.4s过了。

$$O(n^2)$$

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
void read(int &x){
	char ch = getchar();x = 0;
	for (; ch < '0' || ch > '9'; ch = getchar());
	for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
const int maxn = 1e5 + 10;
int n,m,ans,cnt;
int head[maxn],dis[maxn<<1];
struct Edge{
    int to,next,idx;
}G[maxn<<2];
void add(int u,int v,int id){
    G[cnt].to = v;
    G[cnt].next = head[u];
    G[cnt].idx = id;
    head[u] = cnt++;
}
deque<int> q;
void bfs(){
    for(int i = head[1];~i;i=G[i].next) dis[i/2] = 1,q.push_back(i/2);
    while(!q.empty()){
        int now = q.front();
        q.pop_front();
        for(int i = head[G[now*2].to];~i;i=G[i].next){
            if(G[i].idx == G[now*2].idx){
                if(dis[i/2] > dis[now]){
                    dis[i/2] = dis[now];q.push_front(i/2);
                }
            }else{
                if(dis[i/2] > dis[now] + 1){
                    dis[i/2] = dis[now]+1;q.push_back(i/2);
                }
            }
        }
        for(int i = head[G[now*2+1].to];~i;i=G[i].next){
            if(G[i].idx == G[now*2+1].idx){
                if(dis[i/2] > dis[now]){
                    dis[i/2] = dis[now];q.push_front(i/2);
                }
            }else{
                if(dis[i/2] > dis[now]+1){
                    dis[i/2] = dis[now]+1;q.push_back(i/2);
                }
            }
        }
    }
    ans = INF;
    for(int i = head[n];~i;i=G[i].next){
        if(ans > dis[i/2]) ans = dis[i/2];
    }
}
int main(){
#ifdef LOCAL
    freopen("a.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&m)){
        memset(head,-1,sizeof(int)*(n+2));cnt = 0;
        rep(i,0,m+2) dis[i] = INF;
        rep(i,0,m){
            int u,v,id;read(u);read(v);read(id);
            add(u,v,id);add(v,u,id);
        }
        bfs();
        printf("%d\n",ans==INF?-1:ans);
    }
    return 0;
}