Submission #1690115


Source Code Expand

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const long long INF = (1LL << 60);
using namespace std;

class Edge{
    public:
        long long to, cost;
        Edge(long long to, long long cost) : to(to) ,cost(cost) {}
};

class Node{
    public:
        long long dis;
        bool isUsed;
        Node(){
            this->dis = INF;
            this->isUsed = 0;
        }
        bool operator < ( const Node &right ) const {
            return dis < right.dis;
        }
};

typedef vector<vector<Edge>> AdjList;

long long dijkstra(AdjList g, long long start, long long n, long long r, long long t){
    vector<Node> node(n);
    priority_queue<long long, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;

    q.push(make_pair(0, start));
    node[start].dis = 0;

    pair<long long, long long> u;
    while(not q.empty()){
        u = q.top(); q.pop();
        long long current = u.second;
        node[current].isUsed = 1;

        rep(i,g[current].size()){
            long long next = g[current][i].to;
            if(node[next].isUsed == 0){
                if(node[next].dis > node[current].dis + g[current][i].cost){
                    node[next].dis = node[current].dis + g[current][i].cost;
                    q.push(make_pair(node[next].dis, next));
                }
            }
        }
    }
    sort(all(node));
    rep(i,n) node[i].dis *= t;

	long long ans = 0;
	auto it = node.begin();
	advance(it,1); //ゴール地点を省く

	for(; it != node.end(); it++){
		Node tmp;
		tmp.dis = it->dis / t * r;

		int dif = distance(upper_bound(all(node), tmp), node.end());
		ans += dif;
		if(n - dif <= distance(node.begin(), it)) ans--;
	}
	return ans;

    for(auto it = ++node.begin(); it != node.end(); it++){
        Node tmp;
        tmp.dis = it->dis / t * r;
        tmp.isUsed = true;
        auto next = it;
        next++;
        ans += node.end() - upper_bound(next, node.end(), tmp);
    }
    return ans;
}

int main(){
    long long n, m, r, t;
    cin >> n >> m >> r >> t;

    AdjList g(n);
    rep(i,m){
        long long a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].emplace_back(Edge{b,c});
        g[b].emplace_back(Edge{a,c});
    }

    long long ans = 0;
    rep(i,n){
        ans += dijkstra(g,i,n,r,t);
    }
    cout << ans << endl;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User noy72
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2605 Byte
Status AC
Exec Time 1631 ms
Memory 768 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 18
Set Name Test Cases
Sample subtask0_sample-01.txt, subtask0_sample-02.txt
All subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Case Name Status Exec Time Memory
subtask0_sample-01.txt AC 1 ms 256 KB
subtask0_sample-02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 9 ms 256 KB
subtask1_06.txt AC 12 ms 256 KB
subtask1_07.txt AC 49 ms 512 KB
subtask1_08.txt AC 57 ms 384 KB
subtask1_09.txt AC 487 ms 512 KB
subtask1_10.txt AC 463 ms 512 KB
subtask1_11.txt AC 203 ms 512 KB
subtask1_12.txt AC 1493 ms 640 KB
subtask1_13.txt AC 1487 ms 640 KB
subtask1_14.txt AC 1626 ms 768 KB
subtask1_15.txt AC 1105 ms 768 KB
subtask1_16.txt AC 1631 ms 768 KB