結果

問題 No.789 範囲の合計
ユーザー mtsdmtsd
提出日時 2019-02-08 22:10:42
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,204 bytes
コンパイル時間 875 ms
コンパイル使用メモリ 93,436 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 11:33:03
合計ジャッジ時間 4,244 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 WA -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:23:14: warning: overflow in conversion from ‘double’ to ‘std::vector<int>::value_type’ {aka ‘int’} changes value from ‘1.0e+16’ to ‘2147483647’ [-Woverflow]
   23 | #define inf  1e+16
      |              ^~~~~
main.cpp:31:21: note: in expansion of macro ‘inf’
   31 |     vector<ll> dd(n,inf);
      |                     ^~~
main.cpp:23:14: warning: overflow in conversion from ‘double’ to ‘ll’ {aka ‘int’} changes value from ‘1.0e+16’ to ‘2147483647’ [-Woverflow]
   23 | #define inf  1e+16
      |              ^~~~~
main.cpp:65:14: note: in expansion of macro ‘inf’
   65 |     ll ans = inf;
      |              ^~~
main.cpp:23:14: warning: overflow in conversion from ‘double’ to ‘std::vector<int>::value_type’ {aka ‘int’} changes value from ‘1.0e+16’ to ‘2147483647’ [-Woverflow]
   23 | #define inf  1e+16
      |              ^~~~~
main.cpp:68:24: note: in expansion of macro ‘inf’
   68 |         vector<ll> d(n,inf);
      |                        ^~~
main.cpp:85:17: warning: overflow in conversion from ‘double’ to ‘ll’ {aka ‘int’} changes value from ‘-1.0e+16’ to ‘-2147483648’ [-Woverflow]
   85 |         ll ma = -inf;
      |                 ^

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  int ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1e+16
#define rep(i,n) for(int i=0;i<(int)(n);++i)

vector<vector<pair<ll,int> > > g;

int main(){
    int n,m,s;
    cin >> n >> m >> s;
    vector<ll> dd(n,inf);
    vector<ll> t(n);
    int cnt=0;
    rep(i,n){
        cin >> t[i]; 
        if(t[i]>0)cnt++;
    }
    if(cnt==1){
        cout << 0 << endl;
        return 0;
    }
    s--;
    g.resize(n);
    rep(i,m){
        int a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        g[a].push_back(MP(c,b));
        g[b].push_back(MP(c,a));
    }
    dd[s] = 0;
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> >  >pq;
    pq.push(MP(0,s));
    while(!pq.empty()){
        auto x = pq.top();
        pq.pop();
        if(dd[x.second]!=x.first)continue;
        for(auto y:g[x.second]){
            if(dd[y.second]>dd[x.second]+y.first){
                dd[y.second] = dd[x.second]+y.first;
                pq.push(MP(dd[y.second],y.second));
            }
        }
    }   
    ll ans = inf;
    for(int i=0;i<n;i++){
        pq.push(MP(0,i));
        vector<ll> d(n,inf);
        d[i] = 0;
        while(!pq.empty()){
            auto x = pq.top();
            pq.pop();
            if(d[x.second]!=x.first)continue;
            for(auto y:g[x.second]){
                if(d[y.second]>d[x.second]+y.first){
                    d[y.second] = d[x.second]+y.first;
                    pq.push(MP(d[y.second],y.second));
                }
            }
        }
        ll tmp = 0;
        rep(j,n){
            tmp += 2*d[j]*t[j];
        }
        ll ma = -inf;
        rep(j,n){
            if(t[j]>0){
                ma = max(ma,d[j]-dd[j]);
            }
        }
        tmp -= ma;
        //cerr << tmp << endl;
        ans = min(ans,tmp);
    }
    cout << ans << endl;
    return 0;
}
0