1486E - Paired Payment（多元最短路）

1486E - Paired Payment

傳送門

題意

給定一個不保證連通的無向圖，每次走都必須連着走兩條路（ a , b , c a, b, c a,b,c 三個點，則隻能走 a b — b c ab—bc ab—bc 到 c c c ，或者 a c — c b ac—cb ac—cb 到 b b b ），且所花費的金錢為兩條路的邊權和的平方（ ( w a b + w b c ) 2 (w_{ab} + w_{bc})^2 (wab​+wbc​)2 ）。問從第一個點到其他所有點花費的最小金額各是多少？沒有路徑輸出-1。

思路

參考：

E. Paired Payment(多元最短路dijkstra)

Codeforces-1486 E. Paired Payment（多元最短路

普通的dijtra是用

cost[v]

表示起點到點 v v v 的最短路徑（這題問的是價格，就用cost來呼應了），原來的轉移方程式為：

if(cost[nxt.v] > nxt.w + now.w){
	cost[nxt.v] = nxt.w + now.w;//松弛
	que.push(nxt.v, cost[nxt.v]);//加入隊列
}
           

這裡我們用

cost[v][w][num]

表示從起點到點 v v v ，上一個點的邊權是 w w w ，此時一共經過了 n u m num num 個點。因為 n u m num num 對答案的影響隻是在于其奇偶性（奇數個需要計算上一個點邊權+目前點邊權和的平方，偶數個不需要），是以 n u m num num 的取值可以壓縮為0，1。現在的轉移方程式變為：

co = now.num ?  (now.w + nxt.w) * (now.w + nxt.w) : 0;//是否需要加上權值
if(cost[nxt.v][nxt.w][now.num ^ 1] > cost[now.v][now.w][now.num] + co){
	cost[nxt.v][nxt.w][now.num ^ 1] = cost[now.v][now.w][now.num] + co;
	que.push({nxt.v,
              nxt.w,
              cost[nxt.v][nxt.w][now.num ^ 1],
              now.num ^ 1});
}
           

其主要的思路就是讓數組

cost

存儲更多的資訊。

代碼

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e5 + 19;
const ll mod = 1e9 + 7;

struct edge
{
    ll v, w;
    edge() {}
    edge(ll vv, ll ww)
    {
        v = vv;
        w = ww;
    }
};

struct node
{
    ll v, w, sum, num;
    bool operator < (const node& a) const
    {
        return sum > a.sum;
    }
};

vector<edge> es[N];
priority_queue<node> que;
ll cost[N][55][3];
int n, m;

void addEdge(int u, int v, int w)
{
    es[u].push_back(edge(v, w));
    es[v].push_back(edge(u, w));
}

void dij(int s)
{
    memset(cost, INF, sizeof(cost));
    cost[s][0][0] = 0;
    que.push({s, 0, 0, 0});
    while(!que.empty())
    {
        node now = que.top();
        que.pop();
        for(int i = 0; i < es[now.v].size(); i++)
        {
            edge nxt = es[now.v][i];
            ll co = now.num ?  (now.w + nxt.w) * (now.w + nxt.w) : 0;
            if(cost[nxt.v][nxt.w][now.num ^ 1] > cost[now.v][now.w][now.num] + co)
            {
                cost[nxt.v][nxt.w][now.num ^ 1] = cost[now.v][now.w][now.num] + co;
                que.push({nxt.v,
                         nxt.w,
                         cost[nxt.v][nxt.w][now.num ^ 1],
                         now.num ^ 1});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0, u, v, w; i < m; i++)
    {
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    dij(1);
    for(int i = 1; i <= n; i++)
    {
        ll ans = INF;
        for(int j = 0; j <= 50; j++)
            ans = min(ans, cost[i][j][0]);
        if(ans == INF)
        {
            cout << -1 << ' ';
            continue;
        }
        cout << ans << ' ';
    }
    cout << endl;
    return 0;
}