21 Days Trainging // Day 5

1. trace

My ideas :

1. Calculate the length of the shortest path first.
2. For every query, do step 1 again and compare the result.
3. If p_i=0, directly output "SOSO".

Code (Not std BF):

#include 
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    long long u, v, w;
};

map<long long, map > G;
long long N, M;
long long shortestpath() {
    set vis;
    vector<vector > dp;
    for (long long i=0;i<N;i++) {
        dp.push_back(vector(N));
        for (long long j=0;j<N;j++)  dp[i][j]=INF;
    }
    for (long long i=0;i<N;i++) dp[i][i] = 0;
    queue<pair > Q;
    Q.push(make_pair(0, 0));
    while (!Q.empty()) {
        pair cur=Q.front();Q.pop();
        long long node=cur.second, dist=cur.first;
        if (vis.find(node)!=vis.end()) continue;
        vis.insert(node);
        for (map::iterator it=G[node].begin();it!=G[node].end();it++) {
            if (dp[0][it->first] > dist+it->second) {
                dp[0][it->first] = dist+it->second;
                Q.push(make_pair(dp[0][it->first], it->first));
            }
        }
    }
    return dp[0][1];
}

int main() {
    freopen("trace.in", "r", stdin);
    freopen("trace.out", "w", stdout);
    cin >> N >> M;
    string wave;cin >> wave;
    Edge Es[M];
    for (long long i=0;i> u >> v >> w;u--;v--;
        if (G.find(u)==G.end()) G[u]=map();
        G[u][v] = w;
        Es[i] = {u, v, w};
    } 
    long long T0 = shortestpath();
    cout << T0 << endl;
    for (long long i=0;iT0) cout << "SAD";
            if (Tx==T0) cout << "SOSO";
            if (Tx<T0) cout << "HAPPY";
            G[Es[i].u][Es[i].v]=Es[i].w;
            G[Es[i].v].erase(Es[i].u);
        }
        else cout << "SOSO";
        cout << endl;
    }
    return 0;
}

Constraints :

Expected : (0/8)/8