poj 1511 Invitation Cards (链式前向星存图+spfa)
poj 1511 题目链接 题意:和那道奶牛的舞会类似,要求所有点到点1的距离和加上1点到所有点的距离和。 思路:正反存边建两次图,跑两次spfa. 然而用vector会TLE....所以去学习了新的建图方式。。。也就是链式前向星:链式前向星(边表)学习链接 也叫边表。
是一种几乎没有什么缺点的存图方式。。。? 比起普通的前向星少了个排序。
哦,还有我发现貌似很多人把这个东西叫邻接表。。但是根据这里:几种建图方式
这个东西还是交边表或者链式前向星比较合适。。。?
/* ***********************************************
Author :111qqz
Created Time :2016年05月23日 星期一 20时31分19秒
File Name :code/poj/1511.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E7+7;
7LL d[N];
8bool inq[N];
9int n,m;
10struct Edge
11{
12 int v,w;
13 int nxt;
14}edge1[N],edge2[N]; //反向存一次
15int head1[N],head2[N];
16int cnt;
17void addedge(Edge *edge,int *head,int u,int v,int w)
18{
19 edge[cnt].v = v;
20 edge[cnt].w = w;
21 edge[cnt].nxt = head[u];
22 head[u] = cnt;
23 cnt++;
24}
LL spfa(Edge *edge,int *head)
{
1 ms(inq,false);
2 for ( int i = 0 ; i <= n ; i++) d[i] = 1E18;
3 queue<int>q;
4 q.push(1);
5 d[1] = 0 ;
6 inq[1] = true;
1 while (!q.empty())
2 {
3 int u = q.front();
4 q.pop();
5 inq[u] = false;
1 for ( int i = head[u]; i !=-1 ;i=edge[i].nxt)
2 {
3 int v = edge[i].v;
4 int w = edge[i].w;
1 if (d[v]>d[u]+w)
2 {
3 d[v] = d[u] + w;
4 if (inq[v]) continue;
5 inq[v] = true;
6 q.push(v);
7 }
8 }
// cout<<"sadsad"<<endl;
1 }
2 LL res = 0 ;
3 for ( int i = 2 ; i <= n ; i++) res +=d[i];
4 // cout<<"res:"<<res<<endl;
5 //
1 return res;
2}
3int main()
4{
5 #ifndef ONLINE_JUDGE
6 freopen("code/in.txt","r",stdin);
7 #endif
1// ios::sync_with_stdio(false);
2 int T;
3 scanf("%d",&T);
4 while (T--)
5 {
6 scanf("%d%d",&n,&m);
7 cnt = 0;
8 ms(head1,-1);
9 ms(head2,-1); //忘记初始化,智力-2
10 for ( int i = 1 ; i <= m ; i++)
11 {
12 int u,v,w;
13 scanf("%d%d%d",&u,&v,&w);
14 addedge(edge1,head1,u,v,w);
15 addedge(edge2,head2,v,u,w);
}
// cout<<"sadasdadsasd"<<endl;
1 LL ans = 0 ;
2 ans = spfa(edge1,head1)+spfa(edge2,head2);
3 printf("%lld\n",ans);
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}