有两天没有做题了,过年实在是事情很多,今天无论如何也要做一道题啦
这道题,单源点最短路径,我首先想到的时候Dijskra算法,由于数据规模大,有邻接表实现结果超时,第一次提交还time error,由于我没有注意到边是双向的,e的大小应该是m的2倍。
于是用SPFA,ac了。
由于点和边都超多,所以D算法超时,按照正常情况,D算法的时间复杂度是N*N,S算法是M*N,这道我分析了一下,原本以为是D比较好,但是由于是邻接表,记录的是边,那么这种情况下,D算法就需要优化,因为所有的边的都会被遍历两次,这时候时间明显就大于了S算法了
我在网上看,还有人用的是dij和优先队列的结合,博客 http://www.cnblogs.com/Yu2012/archive/2011/11/29/2268442.html
下面是AC代码:
#include <cstdio> #include <queue> #include <cstring> using namespace std; const int N = 20010; const int M = 50010; struct edge { int from, to, w, next; }e[M*2]; int icase, n, m, s, t, idx, head[N]; void add ( int u, int v, int w ) { e[idx].next = head[u]; e[idx].from = u, e[idx].to = v, e[idx].w = w; head[u] = idx++; e[idx].next = head[v]; e[idx].from = v, e[idx].to = u, e[idx].w = w; head[v] = idx++; } int spfa() { queue <int> q; bool vis[N]; memset(vis, 0, sizeof(vis)); q.push(s); int d[N]; for ( int i = 0; i < n; ++i ) d[i] = 500000000; d[s] = 0; while ( !q.empty() ) { int u = q.front(); q.pop(); vis[u] = 0; for ( int i = head[u]; i != -1; i = e[i].next ) { int v = e[i].to, w = e[i].w; if ( d[v] > d[u] + w ) { d[v] = d[u] + w; if ( !vis[v] ) { q.push(v); vis[v] = 1; } } } } return d[t]; } int main() { scanf("%d", &icase); int T = 1; while ( icase-- ) { scanf("%d%d%d%d", &n, &m, &s, &t); idx = 0; for ( int i = 0; i < n; ++i ) head[i] = -1; for ( int i = 0; i < m; ++i ) { int from, to, w; scanf("%d%d%d", &from, &to, &w); add(from, to, w); } int ans = spfa(); printf("Case #%d: ", T++); if ( ans < 500000000 ) printf("%d\n", ans); else printf("unreachable\n"); } }