其实虽然一开始有被这个题的8000MS 和 256MB限制又被吓到 但是严格来说跟之前的POJ 3268是一样的做法只是数据大了点
但是问题就出在数据大了点上 其实严格来说也不大 1e6 数组加起来大概1e7 然后RE了
C Free上死活测不出问题了之后想到用VS来debug然后发现爆栈 然后一块块注释 最后查出原因是数组开在了函数内
但是为什么开在外面就可以了呢 然后我又去问了学长们 然后去看了这个文章 C语言中内存分配
真是一场血案............. 不过学到了很多 栈 堆 全局静态变量区 代码区 数据区 五个区的关系 虽然只是粗浅了解但是还是收益很大
然后明白了C Primer Plus 确实是入门书啊.......连malloc 和alloc的区别都没说 而且也没说到malloc原来可以独享一个区的空间....
以及VS用来debug RE问题真丝好用 C Free上总是莫名其妙得完美运行啊摔
以后有空必须看看龙书了=.=
#include <iostream> #include <string> #include <cstdio> #include <cmath> #include <cstring> #include <queue> #include <map> #include <vector> #include <set> #include <algorithm> #define INF 0x3F3F3F3F using namespace std; const int MAXN = 1e6 + 10; const int MAXM = 1e6 + 10; typedef pair<int, int> pii; struct cmp{ bool operator () (const pii a, const pii b){ return a.first > b.first; } }; int size, head[MAXN], val[MAXM], point[MAXM], next[MAXM]; int t, n, m, dis[MAXN]; int a[MAXM], b[MAXM], value[MAXM]; void init() { size = 0; memset(head, -1, sizeof head); } inline void add(int from, int to, int value) { val[size] = value; point[size] = to; next[size] = head[from]; head[from] = size++; } long long dij(int s) { memset(dis, 0x3f, sizeof dis); priority_queue<pii, vector<pii>, cmp> q; dis[s] = 0; q.push(make_pair(0, s)); while(!q.empty()){ pii u = q.top(); q.pop(); if(u.first > dis[u.second]) continue; for(int i = head[u.second]; ~i; i = next[i]){ int j = point[i]; if(dis[j] > dis[u.second] + val[i]){ dis[j] = dis[u.second] + val[i]; q.push(make_pair(dis[j], j)); } } } long long sum = 0; for(int i = 1; i <= n; i++){ sum += dis[i]; } return sum; } int main() { scanf("%d", &t); while(t--){ long long ans; scanf("%d%d", &n, &m); init(); for(int i = 1; i <= m; i++){ scanf("%d%d%d", &a[i], &b[i], &value[i]); add(a[i], b[i], value[i]); } ans = dij(1); init(); for(int i = 1; i <= m; i++){ add(b[i], a[i], value[i]); } ans += dij(1); printf("%I64d\n", ans); } return 0; }
kuangbin_ShortPathJ (POJ 1511)
原文：http://www.cnblogs.com/quasar/p/5084050.html