POJ 1511 Invitation Cards
http://poj.org/problem?id=1511
题目大意：给出n个点和n条有向边，求所有点到源点1的来回最短路之和（保证每个点都可以往返源点1）
单源点来回最短距离问题，可以调用一次迪杰斯特拉之后将地图反过来再调用一次迪杰斯特拉，两个结果之和就是结果。
但是，此题数据过大，用普通的迪杰斯特拉模板绝对是不行的，需要用到迪杰斯特拉的优先队列实现的模板。
最近才学到的用优先队列优化后的迪杰斯特拉算法。。
先贴模板吧。
//Asimple HDU 1874
#include<bits/stdc++.h>
#define INF 0xfffffff
using namespace std;
const int maxn = 1005;
struct node {
int to;
int w;
node(){
}
node(int to, int w) : to(to), w(w) {
}
bool operator < (const node& a) const {
return w>a.w;
}
};
vector<node> e[maxn];
int n, m;
int dis[maxn];
void init() {
for(int i=0; i<maxn; i++) {
e[i].clear();
dis[i] = INF;
}
}
void Dijkstra(int st, int ed) {
priority_queue<node> q;
dis[st] = 0;
q.push(node(st,dis[st]));
while( !q.empty() ) {
node now = q.top();
q.pop();
for(int i=0; i<e[now.to].size(); i++) {
node y = e[now.to][i];
if( dis[y.to]>now.w+y.w) {
dis[y.to] = now.w + y.w;
q.push(node(y.to, dis[y.to]));
}
}
}
if( dis[ed]==INF) printf("-1\n");
else printf("%d\n", dis[ed]);
}
int main() {
while( cin >> n >> m ) {
init();
for(int i=0; i<m; i++) {
int x, y, num;
scanf("%d %d %d", &x, &y, &num);
e[x].push_back(node(y,num));
e[y].push_back(node(x,num));
}
int s, t;
scanf("%d%d",&s, &t);
Dijkstra(s, t);
}
return 0;
}
做的时候错了十几遍。实在受不了了。百度了大佬们的题解。发现原来是INF设小了。。
//Asimple //#include <bits/stdc++.h> #include <iostream> #include <sstream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <cctype> #include <cstdlib> #include <stack> #include <cmath> #include <set> #include <map> #include <string> #include <queue> #include <limits.h> #include <time.h> #define INF 1e10 #define mod 999101 #define PI 3.14159265358979323 #define swap(a,b,t) t = a, a = b, b = t #define CLS(a, v) memset(a, v, sizeof(a)) #define debug(a) cout << #a << " = " << a <<endl using namespace std; typedef long long ll; const int maxn = 1000005; int n, m, num, T, k, len, ans, sum, x, y; ll dis[maxn]; int fa[maxn]; bool vis[maxn];
struct node{ int y; int v; node( int y, int v) : y(y), v(v) { } node (){ } bool operator < (const node &a) const { return dis[y]>dis[a.y]; } }; struct eg{ int now; int w; int next; }; eg e[maxn]; int a[maxn][3]; void adde(int y, int x, int w) { e[len].now = x; e[len].w = w; e[len].next = fa[y]; fa[y] = len++; } void init() { len = 0; for(int i=0; i<=n; i++) { fa[i] = -1; dis[i] = INF; vis[i] = false; } } ll solve() { priority_queue<node> q; dis[1] = 0; q.push(node(1, dis[1])); while( !q.empty() ) { node pp = q.top(); q.pop(); if( vis[pp.y] ) continue; vis[pp.y] = true; for(int i=fa[pp.y]; i!=-1; i=e[i].next){ int yy = e[i].now; int cost = e[i].w; if( dis[yy]>dis[pp.y]+cost){ dis[yy] = dis[pp.y]+cost; q.push(node(yy,dis[yy])); } } } ll res = 0; for(int i=1; i<=n; i++) { res += dis[i]; } return res; } void input() { for(scanf("%d", &T); T--; ){ scanf("%d %d", &n, &m); init(); for(int i=0; i<m; i++) { scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]); adde(a[i][0], a[i][1], a[i][2]); } ll cnt = solve(); init(); CLS(e, 0); for(int i=0; i<m; i++) adde(a[i][1], a[i][0], a[i][2]); cnt += solve(); printf("%lld\n", cnt); } } int main(){ input(); return 0; }
