Codeforces Round #372 (Div. 2) D. Complete The Graph 图论、最短路、Dijkstra、路径、分配部分边权

Source

Codeforces Round #372 (Div. 2)

My Solution

图论、最短路、Dijkstra、路径、分配部分边权

首先去点2种不可能的情况：

1、不记录w == 0 的边的情况下，求出dis[e]， 如果 dis[e] < L， 则 w == 0 的边无论怎样分配权值，src 到 e 的最短路 都是这个 dis[e]， ans = “NO";

2、把w == 0 的边赋值为1，然后把这些 w == 0的边记录下来，跑一边 Dijkstra，如果 dis[e] > L， 则 由于 w > 0 即 w >= 1， 则无论怎样dis[e] 都大于 L， ans = ”NO“;

然后其它时候都是有答案的

也是把 w == 0的边都赋值为1，然后跑一遍 Dijkstra，得到最短路 dis[e]，但 dis[e] == L，则ok， 否则 对于 这条最短路径上任意一个赋值非1的variabel edgae += L - dise[e]，然后再跑 Dijkstra，如此循环，由于每一个 varible edge最多在 variabel edgae += L - dise[e]的一次， 所以这样的循环最多执行n次就会得到答案

复杂度 O(nmlogn)

​
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> ii;
const int maxn = 1e6 + 8;
const LL INF = 9e18;
vector<ii> G[maxn];
LL dis[maxn], n, src, L;

//O(nlogn)
void dijkstra()
{
    for(int i = 0; i < n; i++) dis[i] = INF;
    dis[src] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, src));
	LL u, d, sz, v, w;
	while(!pq.empty()){
        u = pq.top().second; d = pq.top().first; pq.pop();
        sz = G[u].size();
		for(int i = 0; i < sz; i++){
			v = G[u][i].first; w = G[u][i].second;
			if(d + w < dis[v]){
				dis[v] = d + w;
				pq.push(ii(dis[v], v));
			}
		}
	}
}

vector<ii> g2[maxn];
LL dis2[maxn];

//O(nlogn)
void dijkstra2()
{
    for(int i = 0; i < n; i++) dis2[i] = INF;
    dis2[src] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, src));
	LL u, d, sz, v, w;
	while(!pq.empty()){
        u = pq.top().second; d = pq.top().first; pq.pop();
        sz = g2[u].size();
		for(int i = 0; i < sz; i++){
			v = g2[u][i].first; w = g2[u][i].second;
			if(d + w < dis2[v]){
				dis2[v] = d + w;
				pq.push(ii(dis2[v], v));
			}
		}
	}
}

map<ii, int> variable, haveprint;
void update(const LL& x)
{
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, src));
	LL u, d, sz, v, w;
	while(!pq.empty()){
        u = pq.top().second; d = pq.top().first; pq.pop();
        sz = g2[u].size();
		for(int i = 0; i < sz; i++){
			v = g2[u][i].first; w = g2[u][i].second;
			if(d + w == dis2[v]){
				if(w == 1 && variable[ii(u, v)] == 1){ //w == 1 表示之前没有被更改过
                    g2[u][i].second += x;
                    int sz2 = g2[v].size();                            //无向边是双向读入，所以2个方向的边权都要更新
                    for(int k = 0; k < sz2; k++){
                        if(g2[v][k].first == u){
                            g2[v][k].second += x;
                            break;
                        }
                    }
                    return;
				}
				else{
                    pq.push(ii(dis2[v], v));
				}
			}
		}
	}
}


int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL m, e, u, v, w;
    cin >> n >> m >> L >> src >> e;
    while(m--){
        cin >> u >> v >> w;
        if(w != 0){
            G[u].push_back(ii(v, w));
            G[v].push_back(ii(u, w));
            g2[u].push_back(ii(v, w));
            g2[v].push_back(ii(u, w));
        }
        else{
            variable[ii(u, v)] = 1;
            variable[ii(v, u)] = 1;
            g2[u].push_back(ii(v, 1));
            g2[v].push_back(ii(u, 1));
        }

    }

    dijkstra();
    if(dis[e] < L){
        cout << "NO" << endl;
    }
    else{
        dijkstra2();
        if(dis2[e] > L){
            cout << "NO" << endl;
        }
        else{

            while(dis2[e] != L){
                update(L - dis2[e]);
                dijkstra2();
            }

            cout << "YES" << endl;
            int sz;
            for(int i = 0; i < n; i++){
                sz = g2[i].size();
                for(int j = 0; j < sz; j++){
                    if(haveprint[ii(i, g2[i][j].first)] == 0 && g2[i][j].second != 0){
                        cout << i << " " << g2[i][j].first << " " << g2[i][j].second << "\n";
                        haveprint[ii(i, g2[i][j].first)] = 1;
                        haveprint[ii(g2[i][j].first, i)] = 1;
                    }
                }
            }
        }
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

​

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx