Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.4 kB
2
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

#define PRE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl '\n'

int n, a, b, src;
vector<vector<pair<int, int>>> adj;
vector<int> dist, vis;

void dijkstras(int src) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	dist[src] = 0;
	pq.push({dist[src], src});

	while(!pq.empty()) {
		int node = pq.top().second;
		pq.pop();

		if(vis[node]) continue;
		vis[node] = 1;

		for(auto v : adj[node]) {
			int nbd = v.first;
			int nbd_dist = v.second;
			if(dist[nbd] > dist[node] + nbd_dist) {
				dist[nbd] = dist[node] + nbd_dist;
				pq.push({dist[nbd], nbd});
			}
		}
	}
}

signed main() {
	PRE
    cin >> n >> a >> b;
    map<int, vector<int>> map;
    for(int i=1;i<=n;i++) {
    	int num;
    	cin >> num;
    	map[num].push_back(i);
    }
    	
    int d = map.size();
    adj.resize(n+d+1);

    for(int i=1;i<n;i++) {
    	adj[i].push_back({i+1, b});
    	adj[i+1].push_back({i, b});
    }

    int node = n+1;
    for(auto v : map) {
    	for(auto u : v.second) {
    		adj[u].push_back({node, 0});
    		adj[node].push_back({u, a});
    	}
    	node++;
    }

    dist.assign(n+d+1, 1e18);
    vis.assign(n+d+1, 0);

    cin >> src;
    dijkstras(src);

    for(int i=1;i<=n;i++) 
    	cout << dist[i] << " ";

    return 0;
}
Leave a Comment