Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define debug(x) cerr << '[' << (#x) << "] = " << x << '\n'
- template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
- void Dijkstra(int st); void Clear();
- void PruneShop(); void HashShop();
- const int INF = 1e8 + 8;
- int N, M, S;
- int dist[500][500], dist2[15][15];
- pair<int,int> dp[15][1<<15];
- vector<int>shop, finish(15), start(15);
- vector<pair<int,int>>g[500];
- pair<int,int> solve(int sh, int mask) {
- pair<int,int> &ret = dp[sh][mask];
- if(ret.second!=-1) return dp[sh][mask];
- ret = {0, 0};
- for(int i=0; i<S; ++i) if(dist2[sh][shop[i]]!=INF && (~mask >> i & 1)) {
- pair<int,int>got = solve(shop[i], mask|(1<<i));
- got.second += dist2[sh][shop[i]];
- if(ret.first==got.first) ret = min(ret, got);
- else if(ret.first<got.first) ret = got;
- }
- if(ret.first==0) ret.second = finish[sh];
- ret.first += binary_search(shop.begin(), shop.end(), sh);
- return ret;
- }
- void PlayGround(int T) {
- cin >> N >> M >> S;
- Clear();
- for(int i=0; i<S; ++i) {
- int sh; cin >> sh;
- shop.push_back(sh);
- }
- for(int i=0; i<M; ++i) {
- int u, v, w; cin >> u >> v >> w;
- g[u].push_back(make_pair(v, w));
- }
- for(int i=0; i<S; ++i) Dijkstra(shop[i]);
- Dijkstra(0);
- if(dist[0][N-1]==INF) {
- cout << "Case " << T << ": Impossible\n";
- return;
- }
- debug(dist[0][N-1]);
- PruneShop();
- HashShop();
- pair<int,int>ans = {-1, INT_MAX};
- for(int i=0; i<S; ++i) {
- pair<int,int>cand = solve(shop[i], (1<<i));
- cand.second += start[shop[i]];
- if(ans.first==cand.first) ans = min(ans, cand);
- else if(ans.first < cand.first) ans = cand;
- }
- cout << "Case " << T << ": " << ans.first << ' ' << ans.second << '\n';
- #ifndef ONLINE_JUDGE
- cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- #endif
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- #endif
- int T;
- cin >> T;
- for(int i=1; i<=T; ++i)
- PlayGround(i);
- return 0;
- }
- void Clear() {
- for(int i=0; i<S; ++i) {
- for(int j=0; j<(1<<S); ++j) {
- dp[i][j] = make_pair(-1, -1);
- }
- }
- shop.clear();
- for(int i=0; i<N; ++i) {
- for(int j=0; j<N; ++j)
- dist[i][j] = INF;
- dist[i][i] = 0;
- }
- for(int i=0; i<N; ++i) g[i].clear();
- }
- void HashShop() {
- map<int,int>H;
- for(auto it : shop) H[it] = 1;
- int cnt = 0;
- for(auto &it : H) it.second = cnt++;
- for(int i=0; i<S; ++i) {
- for(int j=0; j<S; ++j) {
- dist2[H[shop[i]]][H[shop[j]]] = dist[shop[i]][shop[j]];
- }
- finish[H[shop[i]]] = dist[shop[i]][N-1];
- start[H[shop[i]]] = dist[0][shop[i]];
- }
- for(auto &it : shop) it = H[it];
- }
- void PruneShop() {
- vector<int>shop2;
- for(int i=0; i<S; ++i) if(dist[shop[i]][N-1]!=INF && dist[0][shop[i]]!=INF) {
- shop2.push_back(shop[i]);
- }
- swap(shop2, shop);
- shop2.clear();
- S = shop.size();
- }
- void Dijkstra(int st) {
- priority_queue<pair<int,int>>pq;
- pq.push({0, st});
- while(!pq.empty()) {
- int cur = pq.top().second;
- pq.pop();
- for(auto it : g[cur]) if(dist[st][cur] + it.second < dist[st][it.first]) {
- dist[st][it.first] = dist[st][cur] + it.second;
- pq.push({-dist[st][it.first], it.first});
- }
- }
- }
Add Comment
Please, Sign In to add comment
