Invitation Cards POJ - 1511 (双向单源最短路)
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.
Input
Output
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 题意:求原点到各个点再回到原点的路径和
思路:直接从原点跑最短路,然后反向建图,再从原点跑一次最短路
#include<cstdio>
#include<cstring>
#include<queue> using namespace std; typedef pair<int,int>p;
typedef long long ll;
struct Node
{
int y,next;
int val;
}node[][]; int cnt[],head[][]; void add(int x,int y,int val,int t)
{
node[t][++cnt[t]].y=y;
node[t][cnt[t]].val=val;
node[t][cnt[t]].next=head[t][x];
head[t][x]=cnt[t];
}
int t;
bool vis[];
ll dist[][];
priority_queue<p,vector<p>,greater<p> >que;
void dijstra(int t)
{
memset(vis,,sizeof(vis));
while(!que.empty())que.pop();
memset(dist[t],0x3f,sizeof(dist[t]));
que.push(p(,));
while(!que.empty())
{
p tmp = que.top();
que.pop();
int s=tmp.second;
int v=tmp.first;
if(vis[s])continue;
vis[s] = ;
dist[t][s]= v;
for(int i=head[t][s];i;i=node[t][i].next)
{
int to=node[t][i].y;
if(dist[t][to] > 1ll*(v+node[t][i].val))
{
que.push(p(v+node[t][i].val,to));
}
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
int p,q;
scanf("%d%d",&p,&q);
cnt[]=cnt[]=;
memset(head,,sizeof(head));
for(int i=;i<=q;i++)
{
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
add(u,v,val,);
add(v,u,val,);
}
dijstra();
dijstra();
ll ans = ;
for(int i=;i<=p;i++)
{
ans += dist[][i] + dist[][i];
}
printf("%lld\n",ans);
}
}
最新文章
- NOIP模拟赛20161114
- Java堆内存的十个要点
- 完全迁移到red hat来的相关问题解决和配置
- Sharepoint的javascript客户端对象模型获取其他站点的list
- 洛谷P3366 【模板】最小生成树
- 使用线程池模拟处理耗时任务,通过websocket提高用户体验
- STL 源码分析《2》----nth_element() 使用与源码分析
- NPOI大数据量多个sheet导出源码(原)
- Storyboards vs NIB vs Code 大辩论
- HCE:Host-based Card Emulation基于Android设备的卡片模拟器
- [转载] HDFS简介
- 彻底解决Yii2中网页刷新时验证码不刷新的问题
- C#杂记-隐式类型的局部变量
- win10下使用powershell来获取文件MD5的命令
- WebStorm File Watchers配置将.less文件编译后的.css输出至指定目录
- FFmpeg: 一个简单测试手机解码效率的方法
- Centos下,Docker部署Yapi接口管理平台(详细得令人发指)
- linux运维发展路线
- Python网络_TCP/IP简介
- Cocos2d-x3.1TestCpp之NewRenderTest Demo分析