http://codeforces.com/problemset/problem/601/A
这道题没想过来, 有点脑筋急转弯的感觉了
本质上就是找最短路径 但是卡在不能重复走同一个点 ---->>> 这是来坑人的
因为这是一个完全图(不是被road 连接 就是被rail连接 ) 所以一定有一条直接连1 和 n的路径
那么只用找没有连 1 和 n 的路径的 那个图的最短路即可
然后这个dijkstra写的是O(V^2)的写法
以后尽量用优先队列的写法O(ElogV)
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define INF 0x3f3f3f3f 5 using namespace std; 6 7 int rail[401][401]; 8 int road[401][401]; 9 int n, m; 10 11 int dijkstra(int town[401][401]) 12 { 13 int dist[401]; 14 bool use[401]; 15 memset(use, 0, sizeof(use)); 16 fill(dist, dist+n+1, INF); 17 dist[1] = 0; 18 while (true) 19 { 20 int v = -1; 21 for (int i = 1; i <= n; i++) 22 { 23 if (!use[i] && (v == -1 || dist[i] < dist[v])) v = i; 24 } 25 if (v == -1) break; 26 use[v] = true; 27 for (int i = 1; i <= n; i++) 28 { 29 dist[i] = min(dist[i], dist[v] + town[v][i]); 30 } 31 } 32 return dist[n]; 33 34 } 35 int main() 36 { 37 freopen("in.txt", "r", stdin); 38 scanf("%d%d", &n, &m); 39 for (int i = 1; i <= n; i++) 40 { 41 for (int j = 1; j <= n; j++) 42 { 43 rail[i][j] = INF; 44 road[i][j] = 1; 45 } 46 } 47 for (int i = 0; i < m; i++) 48 { 49 int x, y; 50 scanf("%d%d", &x, &y); 51 rail[x][y] = 1; 52 rail[y][x] = 1; 53 road[x][y] = INF; 54 road[y][x] = INF; 55 } 56 int ans = 0; 57 if (rail[1][n] == INF || rail[n][1] == INF) ans = dijkstra(rail); 58 else ans = dijkstra(road); 59 if (ans == INF) printf("-1\n"); 60 else printf("%d\n",ans); 61 }
CodeForces - 601A The Two Routes
原文:http://www.cnblogs.com/oscar-cnblogs/p/6390237.html