POJ - 1511 Invitation Cards（Dijkstra，Spfa双向最短路）

POJ - 1511 Invitation Cards

SPFA算法

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 1000010;
int a[N],b[N],c[N];
int h[N],e[N],w[N],ne[N],idx;
int dist[N];//各点到源点的距离
bool st[N];
void add(int a,int b, int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void SPFA(int u)
{
    memset(dist,0x3f,sizeof dist);memset(st,false,sizeof st);dist[u]=0;queue<int> q;q.push(u);st[u]=true;while(q.size()){
    int t=q.front();q.pop();st[t] = false; for(int i=h[t];i!=-1;i=ne[i]){
    int j=e[i];if(dist[j]>dist[t]+w[i]){
    dist[j]=dist[t]+w[i];if(!st[j]){
    st[j]=true;q.push(j);}}}}
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);LL sum=0;idx=0;memset(h,-1,sizeof(h));for(int i=1;i<=m;i++) add(a[i],b[i],c[i]);SPFA(1);for(int i=1;i<=n;i++) sum+=dist[i];idx=0;memset(h,-1,sizeof(h));for(int i=1;i<=m;i++) add(b[i],a[i],c[i]);SPFA(1);for(int i=1;i<=n;i++) sum+=dist[i];printf("%lld\n",sum);}return 0;
}

Dijkstra算法

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1000010;
int a[N],b[N],c[N];
int h[N],e[N],w[N],ne[N],idx;
int dist[N];//各点到源点的距离
bool st[N];
void add(int a,int b, int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void Dijkstra(int u)
{
    memset(dist,0x3f,sizeof(dist));memset(st,false,sizeof st);dist[u]=0;priority_queue<PII,vector<PII>, greater<PII> > heap;heap.push((PII){
    0,u});while(heap.size()){
    PII k=heap.top();heap.pop();int ver=k.second;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i]){
    int j=e[i]; if(dist[j]>dist[ver]+w[i]){
    dist[j]=dist[ver]+w[i];heap.push((PII){
    dist[j],j});}}}
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);LL sum=0;idx=0;memset(h,-1,sizeof(h));for(int i=1;i<=m;i++) add(a[i],b[i],c[i]);Dijkstra(1);for(int i=1;i<=n;i++) sum+=dist[i];idx=0;memset(h,-1,sizeof(h));for(int i=1;i<=m;i++) add(b[i],a[i],c[i]);Dijkstra(1);for(int i=1;i<=n;i++) sum+=dist[i];printf("%lld\n",sum);}return 0;
}