Submission #2443535
Source Code Expand
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> #include <deque> using namespace std; #define mod 1000000007 int main() { while(1){ int n, m, l, s, t; cin >> n >> m >> l >> s >> t; s--; if(n == 0) break; int graph[301][301] = {}; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i != j) graph[i][j] = 10000 * 3000; } } for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; a--; b--; graph[a][b] = c; graph[b][a] = c; } vector<pair<int, int> > restaurant; for(int i = 0; i < l; i++){ int j, e; cin >> j >> e; j--; restaurant.push_back(make_pair(j, e)); } for(int k = 0; k < n; k++){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); } } } vector<vector<int> > result((1 << l), vector<int>(l, mod)); int ans = 0; for(int i = 0; i < l; i++){ int st = restaurant[i].first; int eat = restaurant[i].second; result[(1 << i)][i] = graph[s][st] + eat; if(graph[s][st] + eat + graph[st][s] <= t) ans = 1; } for(int i = 1; i < (1 << l); i++){ for(int j = 0; j < l; j++){ if(result[i][j] == mod) continue; int nowst = restaurant[j].first; for(int k = 0; k < l; k++){ if((i & (1 << k)) > 0) continue; int st = restaurant[k].first; int eat = restaurant[k].second; result[i | (1 << k)][k] = min(result[i | (1 << k)][k], result[i][j] + graph[nowst][st] + eat); } if(result[i][j] + graph[nowst][s] <= t){ int cnt = 0; for(int k = 0; k < l; k++){ if((i & (1 << k)) > 0) cnt++; } ans = max(ans, cnt); } // cout << i << " " << j << " " << result[i][j] << endl; } } cout << ans << endl; } }
Submission Info
Submission Time | |
---|---|
Task | C - SIRO Challenge |
User | maple |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2096 Byte |
Status | AC |
Exec Time | 1302 ms |
Memory | 7296 KB |
Judge Result
Set Name | all | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
all | Merged |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
Merged | AC | 1302 ms | 7296 KB |