TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

50.0% (1/2)

Tags

Description

波奇醬是一個有點內向的女孩,每天都會從家裡到展演廳練習吉他,直到晚上才回家。然而身為社恐的她,覺得背著吉他走在路上會讓路人覺得看起來很酷並吸引路人的目光而讓她飽受壓力受到精神傷害。
為了能最小化受到的傷害,她為地圖上的每條道路根據人流量、時尚度等因素計算出一個分數來量化她經過這條道路會被覺得有多酷,同時也會累積等量的壓力。
而每當她從家裡走到展演廳(反之亦然)後,便會開始回想這段黑歷史而受到精神傷害,其程度等同一路上累積的總壓力值向下取整。
現在給你這個城市地圖,請問波奇醬往返一趟最少會受到多少程度的精神傷害?當然,如果沒有道路能讓她往返那麼她就不用出門不會受到傷害了…吧。

以下為提供的解法,但是卻得到 WA,請在 edit distance 2 以內將該程式碼修改正確:

#include<bits/stdc++.h>
#define ll long long
#define inf (1ll<<50)
#define node int
#define home 0
#define live 1
#define cool double
#define edge pair<node,cool>
#define to first
#define c second
#define pressure double
#define damage ll
#define elem pair<pressure,node>
#define cp first
#define cn second

using namespace std;

int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int n,m; cin>>n>>m;
  vector<vector<edge>> G(n),rG(n);
  for(int i=0;i<m;i++){
    int x; edge e;
    cin>>x>>e.to>>e.c;
    G[x].push_back(e);
    swap(x,e.to);
    rG[x].push_back(e);
  }
  damage ans=0;
  function<bool()> sp=[&](){
    vector<pressure> mp(n,inf);
    vector<bool> v(n);
    priority_queue<elem,vector<elem>,greater<elem>> pq;
    pq.push({mp[home]=0,home});
    while(!pq.empty()){
      int x=pq.top().cn; pq.pop();
      if(v[x]) continue;
      v[x]=1;
      for(const edge &e:G[x]){
        if(!v[e.to]&&mp[e.to]>mp[x]+e.c)
          pq.push({mp[e.to]=mp[x]+e.c,e.to});
      }
    }
    ans+=mp[live];
    return v[live];
  };
  function<bool()> rsp=[&](){
    vector<pressure> mp(n,inf);
    vector<bool> v(n);
    priority_queue<elem,vector<elem>,greater<elem>> pq;
    pq.push({mp[home]=0,home});
    while(!pq.empty()){
      int x=pq.top().cn; pq.pop();
      if(v[x]) continue;
      v[x]=1;
      for(const edge &e:rG[x]){
        if(!v[e.to]&&mp[e.to]>mp[x]+e.c)
          pq.push({mp[e.to]=mp[x]+e.c,e.to});
      }
    }
    ans+=mp[live];
    return v[live];
  };
  if(!sp()||!rsp()) ans=0;
  cout<<ans<<"\n";
  return 0;
}

Input Format

第一行輸入兩個正整數 $N,M$ 分別該城市地圖上的節點和道路數量,其中節點以編號 $0\sim N-1$ 表示。

接下來有 $M$ 行每行有兩個正整數 $x_i,y_i$ 和一個浮點數 $c_i$ 代表第 $i$ 條道路是從節點 $x_i$ 到 $y_i$ 且分數(如題敘所述)為 $c_i$ 的單行道。

其中波奇醬的家在編號為 $0$ 的節點,而展演廳在編號為 $1$ 的節點。

  • $2\le N\le 10^ 5$
  • $0\le M\le 2\times 10^ 5$
  • $0\le x_i,y_i\lt N$
  • $0\le c_i\le 10^ 6$

Output Format

輸出一個整數代表波奇醬往返一趟最少會受到多少程度的精神傷害。如果不存在路徑讓他成功往返一趟,則該數值為 $0$。

Sample Input 1

5 8
1 0 1.918
2 3 3.898
0 1 5.477
3 3 0.781
3 1 2.973
0 0 1.595
3 3 4.321
4 2 2.844

Sample Output 1

6

Sample Input 2

6 12
5 3 7.234
0 0 7.054
0 2 2.144
2 2 1.157
2 1 3.316
5 4 3.771
0 1 6.594
3 5 7.169
4 4 2.156
0 1 6.413
0 3 5.661
1 1 2.506

Sample Output 2

0

Hints

Problem Source

IOICamp 2023 Day1 pD

Subtasks

No. Testdata Range Score
1 0~61 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1
25 1000 65536 65536 1
26 1000 65536 65536 1
27 1000 65536 65536 1
28 1000 65536 65536 1
29 1000 65536 65536 1
30 1000 65536 65536 1
31 1000 65536 65536 1
32 1000 65536 65536 1
33 1000 65536 65536 1
34 1000 65536 65536 1
35 1000 65536 65536 1
36 1000 65536 65536 1
37 1000 65536 65536 1
38 1000 65536 65536 1
39 1000 65536 65536 1
40 1000 65536 65536 1
41 1000 65536 65536 1
42 1000 65536 65536 1
43 1000 65536 65536 1
44 1000 65536 65536 1
45 1000 65536 65536 1
46 1000 65536 65536 1
47 1000 65536 65536 1
48 1000 65536 65536 1
49 1000 65536 65536 1
50 1000 65536 65536 1
51 1000 65536 65536 1
52 1000 65536 65536 1
53 1000 65536 65536 1
54 1000 65536 65536 1
55 1000 65536 65536 1
56 1000 65536 65536 1
57 1000 65536 65536 1
58 1000 65536 65536 1
59 1000 65536 65536 1
60 1000 65536 65536 1
61 1000 65536 65536 1