生活随笔
收集整理的這篇文章主要介紹了
hdu 1535 spfa
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
建個(gè)正向的圖。
建個(gè)反向的圖。
2遍spfa搞定。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int p,q;
const int inf=0x3f3f3f3f;
struct node
{int v,nxt;int w;
}edge[1000005];struct s{int a,b,c;
}record[1000005];
int nume,head[1000005];int dis[1000005];
int inque[1000005];
void add(int u,int v,int w)
{edge[nume].v=v;edge[nume].w=w;edge[nume].nxt=head[u];head[u]=nume++;
}
int ans=0;void spfa(int src){int i;queue<int >que;que.push(src);for(i=1;i<=p;i++) {dis[i]=inf;inque[i]=0;}dis[src]=0;inque[src]=1;while(!que.empty()){int u=que.front();que.pop();inque[u]=0;for(i=head[u]; i!=-1 ; i=edge[i].nxt){int v=edge[i].v;if(dis[u]+edge[i].w<dis[v]){dis[v]=dis[u]+edge[i].w;if(!inque[v]){que.push(v);inque[v]=1;}}}}
}
int main()
{int t;scanf("%d",&t);while(scanf("%d%d",&p,&q)!=EOF){int i;nume=0;memset(head,-1,sizeof(head));for(i=0;i<q;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);record[i].a=a;record[i].b=b;record[i].c=c;add(a,b,c);}ans=0;spfa(1);for(i=2;i<=p;i++) ans+=dis[i];nume=0;memset(head,-1,sizeof(head));for(i=0;i<q;i++){add(record[i].b,record[i].a,record[i].c);}spfa(1);for(i=2;i<=p;i++) ans+=dis[i];printf("%d\n",ans);}
}
總結(jié)
以上是生活随笔為你收集整理的hdu 1535 spfa的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
