提出詳細

ソースコード

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define sz size()
#define endl "\n"
#define print(X) cout << (X) << "\n"
#define answer(p) printf("Case #%lld:\n",(p)+1);
// #define input(X) getline(cin,X)
static const int INF = 1e+9+7;
static const ll INFL = 1e+18+7;
ll n,m,l;
// string s,t;
// ll d[200010],e[200010],dp[1001][1001];
// int field[200][200];

class Dijkstra{
private:
  struct edge{int to,cost;};
  typedef pair<int,int> P;
  vector<edge> graph[100000];
  int ans[100000];

public:
  int vertces,edges;
  Dijkstra(int v = 0, int e = 0){
    vertces = v;
    edges = e;
    // cin >> vertces >> edges;

    for(int i = 0;i < edges;i++){
      int a,b,c;
      cin >> a >> b >> c;
      // a--;b--;
      graph[a].push_back(edge{b,c});
      graph[b].push_back(edge{a,c});
    }
  }

  int goal(int goal){
    return ans[goal];
    // printf("%d\n",ans[goal-1]);
  }

  void process(int s = 0){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(ans,ans+vertces,1e+9+7);
    ans[s] = 0;
    que.push(P(0,s));

    while(!que.empty()){
      P p = que.top();que.pop();
      int v = p.second;
      if(ans[v] < p.first)continue;

      rep(i,0,graph[v].sz){
        edge e = graph[v][i];
        if(ans[e.to] > ans[v]+e.cost){
          ans[e.to] = ans[v] + e.cost;
          que.push(P(ans[e.to],e.to));
        }
      }
    }
  }
};

int main(){
  int p;
  cin >> p;
  rep(q,0,p){
    int start,tensor,goal;
    cin >> n >> m;
    cin >> start >> tensor >> goal;

    Dijkstra dij(n,m);
    dij.process(start);
    int ans1 = dij.goal(tensor);
    dij.process(tensor);
    int ans2 = dij.goal(goal);
    answer(q);
    print(ans1+ans2);
  }
  return 0;
}

提出情報

提出時間 2018-11-16 17:38:19
問題 I - リアルタイムアタック(Large)
ユーザ名 miyajima
状態 正解
正解率 24/24
提出出力結果

テストケース情報

# 状態 詳細情報
テストケース 1 正解 詳細を見る
テストケース 2 正解 詳細を見る
テストケース 3 正解 詳細を見る
テストケース 4 正解 詳細を見る
テストケース 5 正解 詳細を見る
テストケース 6 正解 詳細を見る
テストケース 7 正解 詳細を見る
テストケース 8 正解 詳細を見る
テストケース 9 正解 詳細を見る
テストケース 10 正解 詳細を見る
テストケース 11 正解 詳細を見る
テストケース 12 正解 詳細を見る
テストケース 13 正解 詳細を見る
テストケース 14 正解 詳細を見る
テストケース 15 正解 詳細を見る
テストケース 16 正解 詳細を見る
テストケース 17 正解 詳細を見る
テストケース 18 正解 詳細を見る
テストケース 19 正解 詳細を見る
テストケース 20 正解 詳細を見る
テストケース 21 正解 詳細を見る
テストケース 22 正解 詳細を見る
テストケース 23 正解 詳細を見る
テストケース 24 正解 詳細を見る