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
AC × 1
Set Name Test Cases
all Merged
Case Name Status Exec Time Memory
Merged AC 1302 ms 7296 KB