HDU - 1535 Invitation Cards 前向星SPFA
Invitation Cards
The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where 'X' denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.
All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.
InputThe input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop.
OutputFor each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.
Sample Input
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
Sample Output
46
210 题意:在有向图中,求一个点到所有点的最短路与所有点到这个点的最短路之和。
思路:正反向建图,两边SPFA。由于数据规模较大,这道题用vector过不了,相比之下前向星存图显得效率更高。以下是前向星建图代码。
#include<stdio.h>
#include<string.h>
#include<deque>
#define MAX 1000005
#define INF 10000000000000000
using namespace std; struct Node{
int v,next,w;
}edge[MAX],redge[MAX]; long long dis[MAX],diss[MAX];
int b[MAX],head1[MAX],head2[MAX];
int n,cnt1,cnt2; void Init()
{
cnt1=;
memset(head1,-,sizeof(head1));
cnt2=;
memset(head2,-,sizeof(head2));
} void addEdge(int u,int v,int w)
{
edge[cnt1].v=v;
edge[cnt1].w=w;
edge[cnt1].next=head1[u];
head1[u]=cnt1++;
} void addrEdge(int u,int v,int w)
{
redge[cnt2].v=v;
redge[cnt2].w=w;
redge[cnt2].next=head2[u];
head2[u]=cnt2++;
} void spfa(int k)
{
int i;
deque<int> q;
for(i=;i<=n;i++){
dis[i]=INF;
diss[i]=INF;
}
memset(b,,sizeof(b));
b[k]=;
dis[k]=;
q.push_back(k);
while(q.size()){
int u=q.front();
for(i=head1[u];i!=-;i=edge[i].next){
int v=edge[i].v;
int w=edge[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(b[v]==){
b[v]=;
if(dis[v]>dis[u]) q.push_back(v);
else q.push_front(v);
}
}
}
b[u]=;
q.pop_front();
}
b[k]=;
diss[k]=;
q.push_back(k);
while(q.size()){
int u=q.front();
for(i=head2[u];i!=-;i=redge[i].next){
int v=redge[i].v;
int w=redge[i].w;
if(diss[v]>diss[u]+w){
diss[v]=diss[u]+w;
if(b[v]==){
b[v]=;
if(diss[v]>diss[u]) q.push_back(v);
else q.push_front(v);
}
}
}
b[u]=;
q.pop_front();
}
}
int main()
{
int t,m,u,v,w,i;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
Init();
for(i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addrEdge(v,u,w);
}
spfa();
long long sum=;
for(i=;i<=n;i++){
sum+=dis[i]+diss[i];
}
printf("%lld\n",sum);
}
return ;
}
最新文章
- windows系统常用快捷键及其作用
- python排序算法的实现-快速排序
- vim vi 及其相关插件的使用
- click 绑定(三)防止事件冒泡
- lucene.net 使用过程中的 几个注意事项(含termquery 和QueryParser 的区别)
- openwrt补丁
- JS特效——文字打印机
- struts2+hibernate+spring配置版框架搭建以及简单测试(方便脑补)
- Python学习笔记3
- linux配置分步安装lnmp环境----ghj
- Hadoop+Hbase分布式集群架构“完全篇”
- .Net Core 实践 - 如何在控制台应用(.Net Core)使用appsettings.json配置
- 关于word-break和word-wrap的使用和区别
- gzip解压文件报错
- centos禁止与开启ping设置
- promise 基础知识
- 差分模版题(需理解才明白)AT2442 フェーン現象 (Foehn Phenomena)
- Foxmail Gmail Outlook
- ThreadLocal 与 Request 和 Session 之关联
- C#在服务端验证客户端证书(Certificate)