Submission #754750

#	Time	Username	Problem	Language	Result	Execution time	Memory
754750		bensonlzl	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	382 ms	27068 KiB

commuter_pass

    #include <bits/stdc++.h>
     
    using namespace std;
     
    typedef long long ll;
    typedef pair<ll,ll> pl;
     
    ll N, M, X, Y, S, T, U, V, C, mini = 1e18;
     
     
    ll distS[100005], distT[100005], distU[100005], distV[100005], dp[100005];
    int visit[100005];
    vector<pl> AdjList[100005];
    vector<int> dpList[100005];
     
     
    void dijkstra(int x, ll d[]){
    	priority_queue<pl,vector<pl>,greater<pl> > pq;
    	for (int i = 1; i <= N; ++i) d[i] = 1e16;
     	d[x] = 0;
     	pq.push(pl(0,x));
     	while (!pq.empty()){
     		pl t = pq.top();
     		pq.pop();
     		ll dt = t.first, v = t.second;
     		if (d[v] != dt) continue;
     		for (auto it : AdjList[v]){
     			if (d[it.first] > d[v] + it.second){
     				d[it.first] = d[v] + it.second;
     				pq.push(pl(d[it.first],it.first));
     			}
     		}
     	}
    }
     
    void dfs(int x){
    	visit[x] = 1;
    	for (auto it : dpList[x]){
    		if (!visit[it]) dfs(it);
    		dp[x] = min(dp[x],dp[it]);
    	}
    }
     
    void runDP(ll d1[], ll d2[]){
    	for (int i = 1; i <= N; ++i){
    		dp[i] = d2[i];
    		visit[i] = 0;
    	}
    	for (int i = 1; i <= N; ++i){
    		if (!visit[i]) dfs(i);
    	}
    	for (int i = 1; i <= N; ++i){
    		mini = min(mini,dp[i] + d1[i]);
    	}
    }
     
    int main(){
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);	
    	cin >> N >> M;
    	cin >> S >> T;
    	cin >> U >> V;
    	for (int i = 1; i <= M; ++i){
    		cin >> X >> Y >> C;
    		AdjList[X].push_back(pl(Y,C));
    		AdjList[Y].push_back(pl(X,C));
    	}
    	dijkstra(S,distS); dijkstra(T,distT); dijkstra(U,distU); dijkstra(V,distV);
    	for (int i = 1; i <= N; ++i){
    		for (auto it : AdjList[i]){
    			if (distS[i] + it.second + distT[it.first] == distS[T]){
    				dpList[i].push_back(it.first);
    			}
    		}
    	}
    	runDP(distU,distV);
    	cout << mini << '\n';
    }

• Subtask 1: 16 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45