哭哭，t到宇宙尽头，估计是死循环了，跪求大佬看看

UVA1599 Ideal Path

_hMayuri @ 2023-10-12 15:21:33

用udebug的数据测试了一下应该复杂度没什么问题，求大佬看看是不是哪里死循环了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//一次bfs
ll n, m, cnt;
ll head[200005];
ll nxt[400005];
ll to[400005];
ll val[400005];
ll dp[200005];
string save[200005];
bool vis[200005];
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void add(ll u, ll v, ll w) {
    cnt++;
    nxt[cnt] = head[u];
    to[cnt] = v;
    val[cnt] = w;
    head[u] = cnt;
}
queue<ll> q;
inline void bfs() {
    q.push(n);
    dp[n] = 0;
    vis[n] = true;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        vis[u] = false;
        for (ll i = head[u]; i; i = nxt[i]) {
            ll v = to[i];
            if (dp[v] == -1 || dp[v] >= dp[u] + 1) {
                dp[v] = dp[u] + 1;
                if (save[v] != "")save[v] = min(save[v], to_string(val[i]) + " " + save[u]);
                else
                    save[v] = to_string(val[i]) + " " + save[u];
                if(!vis[v])vis[v]=true,q.push(v);
            }
        }
    }
}

inline void solve() {
    cout << dp[1] << endl;
    if (save[1].back() == ' ')
        save[1].pop_back();
    cout << save[1] << endl;
}
inline void init() {
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    memset(nxt, 0, sizeof(nxt));
    memset(to, 0, sizeof(to));
    for (ll i = 1; i <= n; i++)
        head[i] = 0, save[i] = "", dp[i] = -1;
}
int main()
{
     //freopen("in.txt", "r", stdin);
     //freopen("out.txt", "w", stdout);
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    while (cin >> n >> m) {
        init();
        for (ll i = 1; i <= m; i++) {
            ll u, v, w;
            //cin >> u >> v >> w;
            u = read();
            v = read();
            w = read();
            add(u, v, w);
            add(v, u, w);
        }
        bfs();
        solve();
    }
}

by Y_QWQ_Y @ 2023-11-30 22:21:25

超时too

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, ans = 1e9, cn, a[100001];
struct node{int v, d;};
vector <node> e[100001];
map <int, int> vi[100001];
bool vis[100001];
void dfs (int d, int cnt)
{
    if (d == n)
    {
        ans = min (ans, cnt);
        return;
    }
    vis[d] = 1;
    for (int i = 0; i < e[d].size (); ++ i)if (! vis[e[d][i].v])
    {
        a[cnt] = e[d][i].d;
        dfs (e[d][i].v, cnt + 1);
    }
    vis[d] = 0;
}
bool cmp (node a, node b){return a.d < b.d;}
signed main()
{
    while (scanf ("%d %d", &n, &m))
    {
        for (int i = 0; i < m; ++ i)
        {
            int a, b, c;
            scanf ("%d %d %d", &a, &b, &c);
            bool f = 1;
            if (! vi[a][b])vi[a][b] = vi[b][a] = 1e9;
            else f = 0;
            vi[a][b] = vi[b][a] = min (vi[a][b], c);
            if (f)
            {
                e[a].push_back (node{b, vi[a][b]});
                e[b].push_back (node{a, vi[a][b]});
            }
            if (! f)
            {
                for (int j = 0; j < e[a].size (); ++ j)if (e[a][j].v == b)
                {
                    e[a][j].d = vi[a][b];
                    break;
                }
                for (int j = 0; j < e[b].size (); ++ j)if (e[b][j].v == a)
                {
                    e[b][j].d = vi[a][b];
                    break;
                }
            }
        }
        for (int i = 1; i <= n; ++ i)sort (e[i].begin (), e[i].end (), cmp);
        dfs (1, 0);
        printf ("%d\n", ans);
        for (int i = 0; i < ans; ++ i)
        {
            if (i < ans - 1)printf ("%d ", a[i]);
            else printf ("%d", a[i]);
        }
    }
    return 0;
}

也是死了。。。。。。。

|