文理学院程序设计在线练习


Simplified Travelling Salesman Problem

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 9   Accepted Submission(s): 4
Problem Description

There are n cities in Kingdom xxx and m undirected roads connecting the cities. A travelling salesman starts from city s and wants to travel around the kingdom. Now you need to tell him the shortest path.

Input

Multiple cases (<= 10).
For each test case, the first line consists of three integers n, m, s (1 <= n <= 16, m <= 10000, 1 <= s <= n). Then m lines follow, each line consists of three integers u, v, w (1 <= u, v <= n; 0 <= w <= 100), representing two endpoints and length of a road.

Output

For each test data, output one line, representing answer. If the travelling salesman cannot travel around the kingdom, output -1.

Sample Input
5 5 1
1 2 2
1 3 3
1 4 4
1 5 5
4 5 6
Sample Output
20
Source

2017绍兴市联赛