| Acceteped : 23 | Submit : 61 | |
| Time Limit : 5000 MS | Memory Limit : 65536 KB |
Description |
||
题目描述N(3≤N≤1,000)个城市（编号从1~N），M(N-1≤M≤10,000)条公路连接这些城市，每条公路都是双向通车的。 你想从1号城市出发，到达N号城市，期间你希望通过按顺序经过K(0≤K≤3)个指定的城市（这K+2个城市只允许达到1次），求最短的里程。 输入存在多个样例。 每个样例的第一行是三个整数N，M，K。如果N，M，K为0，则表示输入结束。 以后是M行表示M条公路，每行三个整数x(1≤x≤N),y(1≤y≤N),c(1≤c≤1,000),表示城市x与城市y之间有一条距离为c的公路。输入保证任意两座城市之间至少存在一条路。然后的一行包含K个城市的序号，序号属于[2,N-1]。 输出每行输出一个样例的结果，为一个整数。如果不存在这样的方案，输出“Impossible”。 样例输入3 3 1 样例输出7 |
||
Sample Input |
||
Sample Output |
||
Source |
解题：题目说了，只限起点终点，以及要求的几个点只能访问一次，其他点嘛，呵呵！选择微软的C++编译器，速度快，g++慢得不行
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 1010; 18 struct arc { 19 int to,next; 20 }; 21 int head[maxn],mp[maxn][maxn],tot; 22 int n,m,k,city[5],d[maxn]; 23 bool done[maxn]; 24 arc g[maxn<<10]; 25 priority_queue< pii,vector< pii >,greater< pii > >q; 26 void add(int u,int v) { 27 g[tot].to = v; 28 g[tot].next = head[u]; 29 head[u] = tot++; 30 } 31 void dijkstra(int s,int t) { 32 int i,u,v; 33 for(i = 0; i <= n; i++) { 34 d[i] = INF; 35 done[i] = false; 36 } 37 for(i = 0; i <= k+1; i++) 38 if(city[i] != s && city[i] != t) 39 done[city[i]] = true; 40 while(!q.empty()) q.pop(); 41 d[s] = 0; 42 q.push(make_pair(d[s],s)); 43 while(!q.empty()) { 44 u = q.top().second; 45 q.pop(); 46 if(done[u]) continue; 47 done[u] = true; 48 for(i = head[u]; i != -1; i = g[i].next) { 49 if(d[g[i].to] > d[u]+mp[u][g[i].to]) { 50 d[g[i].to] = d[u]+mp[u][g[i].to]; 51 q.push(make_pair(d[g[i].to],g[i].to)); 52 } 53 } 54 if(done[t]) return; 55 } 56 } 57 int main() { 58 int i,j,u,v,w,sum; 59 while(scanf("%d %d %d",&n,&m,&k),n+m+k) { 60 for(i = 1; i <= n; i++) { 61 head[i] = -1; 62 for(j = 1; j <= n; j++) 63 mp[i][j] = INF; 64 } 65 for(tot = i = 0; i < m; i++) { 66 scanf("%d %d %d",&u,&v,&w); 67 if(mp[u][v] == INF) { 68 mp[u][v] = mp[v][u] = w; 69 add(u,v); 70 add(v,u); 71 } else if(mp[u][v] > w) { 72 mp[u][v] = mp[v][u] = w; 73 } 74 } 75 city[0] = 1; 76 for(i = 1; i <= k; i++) scanf("%d",city+i); 77 city[i] = n; 78 bool flag = true; 79 for(sum = i = 0; i <= k; i++) { 80 dijkstra(city[i],city[i+1]); 81 if(d[city[i+1]] == INF) {flag = false;break;} 82 sum += d[city[i+1]]; 83 } 84 flag?printf("%d ",sum):puts("Impossible"); 85 } 86 return 0; 87 }