Submission #1498619
Source Code Expand
#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<queue> #include<vector> #include<functional> #include<cmath> #include<map> #include<stack> #include<set> #include<numeric> #include<limits> #include<iterator> #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef pair<ll, char> plc; struct edge { int cost; int to; }; ll n, m, k,s,g; ll INF = 1000000000; ll d[110]; vector<pl> cost; vector<edge> G[110]; void dijkstra(int s) { priority_queue<pl, vector<pl>, greater<pl>> q; fill(d, d + n, INF); d[s] = 0; q.push(pl(0, s)); while (!q.empty()) { pl p = q.top(); q.pop(); int v = p.second; if (d[v] < p.first)continue; for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; q.push(pl(d[e.to], e.to)); } } } } ll check() { ll sum = d[g],num = 0; ll temp = sum; ll ans=0,res=0; for (int j = 0; j < k-1; j++) { if (sum >= cost[k - 1].first) { ans += cost[k - 1].second; } else { if (j + 1 < k && sum <= cost[j + 1].first - 1 && sum >= cost[j].first) { ans += cost[j].second; } } } for (int i = 0; i < n; i++) { res = 0; num += d[i]; sum -= d[i]; for (int j = 0; j < k-1; j++) { if (num >= cost[k - 1].first) { res += cost[k - 1].second; } else { if (j + 1 < k && num <= cost[j + 1].first - 1 && num >= cost[j].first) { res += cost[j].second; } } if (sum >= cost[k - 1].first) { res += cost[k - 1].second; } else { if (j + 1 < k && sum <= cost[j + 1].first - 1 && sum >= cost[j].first) { res += cost[j].second; } } } ans = min(ans, res); } return ans; } int main() { cin >> n >> m >> k >> s >> g; cost.resize(k); for (int i = 0; i < m; i++) { int a, b, d; cin >> a >> b >> d; G[a].push_back({d,b}); G[b].push_back({d,a }); } for (int i = 0; i < k; i++) cin >> cost[i].first >> cost[i].second; dijkstra(s); cout << check() << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 切符分割 |
User | jj |
Language | C++14 (GCC 5.4.1) |
Score | 20 |
Code Size | 2254 Byte |
Status | RE |
Exec Time | 97 ms |
Memory | 256 KB |
Judge Result
Set Name | direct | small | large | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 20 / 20 | 0 / 20 | 0 / 100 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
direct | direct/basic_case00, direct/basic_case01, direct/basic_case02, direct/basic_case03, direct/basic_case04 |
small | small/append00, small/append01, small/append02, small/append03, small/append20, small/append21, small/append30, small/basic_case00, small/basic_case01, small/basic_case02, small/basic_case03, small/basic_case04, small/basic_case05, small/basic_case06, small/basic_case07, small/basic_case08, small/basic_case09, small/sample02, small/sample03, small/split00 |
large | large/append10, large/append11, large/append12, large/large_case00, large/large_case01, large/large_case02, large/large_case03 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample00 | AC | 1 ms | 256 KB |
sample01 | AC | 1 ms | 256 KB |
direct/basic_case00 | AC | 1 ms | 256 KB |
direct/basic_case01 | AC | 1 ms | 256 KB |
direct/basic_case02 | AC | 1 ms | 256 KB |
direct/basic_case03 | AC | 1 ms | 256 KB |
direct/basic_case04 | AC | 1 ms | 256 KB |
large/append10 | RE | 96 ms | 256 KB |
large/append11 | RE | 96 ms | 256 KB |
large/append12 | RE | 96 ms | 256 KB |
large/large_case00 | RE | 96 ms | 256 KB |
large/large_case01 | RE | 96 ms | 256 KB |
large/large_case02 | RE | 96 ms | 256 KB |
large/large_case03 | RE | 97 ms | 256 KB |
small/append00 | WA | 1 ms | 256 KB |
small/append01 | WA | 1 ms | 256 KB |
small/append02 | WA | 1 ms | 256 KB |
small/append03 | WA | 1 ms | 256 KB |
small/append20 | WA | 1 ms | 256 KB |
small/append21 | WA | 1 ms | 256 KB |
small/append30 | WA | 1 ms | 256 KB |
small/basic_case00 | AC | 1 ms | 256 KB |
small/basic_case01 | AC | 1 ms | 256 KB |
small/basic_case02 | AC | 1 ms | 256 KB |
small/basic_case03 | AC | 1 ms | 256 KB |
small/basic_case04 | AC | 1 ms | 256 KB |
small/basic_case05 | AC | 1 ms | 256 KB |
small/basic_case06 | AC | 1 ms | 256 KB |
small/basic_case07 | AC | 1 ms | 256 KB |
small/basic_case08 | AC | 1 ms | 256 KB |
small/basic_case09 | AC | 1 ms | 256 KB |
small/sample02 | AC | 1 ms | 256 KB |
small/sample03 | AC | 1 ms | 256 KB |
small/split00 | WA | 1 ms | 256 KB |