POJ-3268
2024-08-26 19:09:55
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 13738 | Accepted: 6195 |
Description
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.
Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
Sample Input
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Sample Output
10
Hint
Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units
/**
题意:最短路中哪个走的路程最大
解法:SPFA
**/
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define maxn 1000 + 10
#define INF 0x3f3f3f3f
using namespace std;
int vis[maxn];
int dist[maxn];
int dist1[maxn];
int flag[maxn];
struct Node
{
int v;
int cost;
Node(int _v,int _cost):v(_v),cost(_cost) {}
};
vector<Node>edge[maxn];
vector<Node>edge1[maxn];
int n,m,p;
void addedge(int u,int v,int w)
{
edge[u].push_back(Node(v,w));
edge1[v].push_back(Node(u,w));
}
void SPFA(int start)
{
memset(vis,,sizeof(vis));
memset(dist,INF,sizeof(dist));
queue<int>que;
que.push(start);
vis[start] = ;
dist[start] = ;
while(!que.empty())
{
int tt = que.front();
que.pop();
vis[tt] = ;
for(int i=; i<edge[tt].size(); i++)
{
int mm = edge[tt][i].v;
if(dist[mm] > dist[tt] + edge[tt][i].cost)
{
dist[mm] = dist[tt] + edge[tt][i].cost;
if(!vis[mm])
{
vis[mm] = ;
que.push(mm);
}
}
}
}
memset(vis,,sizeof(vis));
memset(dist1,INF,sizeof(dist1));
while(!que.empty()) que.pop();
vis[start] = ;
dist1[start] = ;
que.push(start);
while(!que.empty())
{
int tt = que.front();
que.pop();
vis[tt] = ;
for(int i=; i<edge1[tt].size(); i++)
{
int mm = edge1[tt][i].v;
if(dist1[mm] > dist1[tt] + edge1[tt][i].cost)
{
dist1[mm] = dist1[tt] + edge1[tt][i].cost;
if(!vis[mm])
{
vis[mm] = ;
que.push(mm);
}
}
}
}
return ;
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("in.txt","r",stdin);
//#endif // ONLINE_JUDGE
scanf("%d %d %d",&n,&m,&p);
int u,v,w;
for(int i=; i<m; i++)
{
scanf("%d %d %d",&u,&v,&w);
addedge(u,v,w);
}
SPFA(p);
int mmax = -INF;
for(int i=; i<=n; i++)
{
if(dist[i] + dist1[i] > mmax && dist[i] != INF && dist1[i]!= INF )
mmax = dist[i] + dist1[i];
}
printf("%d\n",mmax);
return ;
}
/**
题意:最短路中哪个走的路程最大
解法:SPFA
**/
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define maxn 1000 + 10
#define INF 0x3f3f3f3f
using namespace std;
int vis[maxn];
int dist[maxn];
int dist1[maxn];
int flag[maxn];
struct Node
{
int v;
int cost;
Node(int _v,int _cost):v(_v),cost(_cost) {}
};
vector<Node>edge[maxn];
vector<Node>edge1[maxn];
int n,m,p;
void addedge(int u,int v,int w)
{
edge[u].push_back(Node(v,w));
edge1[v].push_back(Node(u,w));
}
void SPFA(int start)
{
memset(vis,,sizeof(vis));
memset(dist,INF,sizeof(dist));
queue<int>que;
que.push(start);
vis[start] = ;
dist[start] = ;
while(!que.empty())
{
int tt = que.front();
que.pop();
vis[tt] = ;
for(int i=; i<edge[tt].size(); i++)
{
int mm = edge[tt][i].v;
if(dist[mm] > dist[tt] + edge[tt][i].cost)
{
dist[mm] = dist[tt] + edge[tt][i].cost;
if(!vis[mm])
{
vis[mm] = ;
que.push(mm);
}
}
}
}
memset(vis,,sizeof(vis));
memset(dist1,INF,sizeof(dist1));
while(!que.empty()) que.pop();
vis[start] = ;
dist1[start] = ;
que.push(start);
while(!que.empty())
{
int tt = que.front();
que.pop();
vis[tt] = ;
for(int i=; i<edge1[tt].size(); i++)
{
int mm = edge1[tt][i].v;
if(dist1[mm] > dist1[tt] + edge1[tt][i].cost)
{
dist1[mm] = dist1[tt] + edge1[tt][i].cost;
if(!vis[mm])
{
vis[mm] = ;
que.push(mm);
}
}
}
}
return ;
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("in.txt","r",stdin);
//#endif // ONLINE_JUDGE
scanf("%d %d %d",&n,&m,&p);
int u,v,w;
for(int i=; i<m; i++)
{
scanf("%d %d %d",&u,&v,&w);
addedge(u,v,w);
}
SPFA(p);
int mmax = -INF;
for(int i=; i<=n; i++)
{
if(dist[i] + dist1[i] > mmax && dist[i] != INF && dist1[i]!= INF )
mmax = dist[i] + dist1[i];
}
printf("%d\n",mmax);
return ;
}
/**
题意:最短路中哪个走的路程最大
解法:SPFA
**/
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define maxn 1000 + 10
#define INF 0x3f3f3f3f
using namespace std;
int vis[maxn];
int dist[maxn];
int dist1[maxn];
int flag[maxn];
struct Node
{
int v;
int cost;
Node(int _v,int _cost):v(_v),cost(_cost) {}
};
vector<Node>edge[maxn];
vector<Node>edge1[maxn];
int n,m,p;
void addedge(int u,int v,int w)
{
edge[u].push_back(Node(v,w));
edge1[v].push_back(Node(u,w));
}
void SPFA(int start)
{
memset(vis,,sizeof(vis));
memset(dist,INF,sizeof(dist));
queue<int>que;
que.push(start);
vis[start] = ;
dist[start] = ;
while(!que.empty())
{
int tt = que.front();
que.pop();
vis[tt] = ;
for(int i=; i<edge[tt].size(); i++)
{
int mm = edge[tt][i].v;
if(dist[mm] > dist[tt] + edge[tt][i].cost)
{
dist[mm] = dist[tt] + edge[tt][i].cost;
if(!vis[mm])
{
vis[mm] = ;
que.push(mm);
}
}
}
}
memset(vis,,sizeof(vis));
memset(dist1,INF,sizeof(dist1));
while(!que.empty()) que.pop();
vis[start] = ;
dist1[start] = ;
que.push(start);
while(!que.empty())
{
int tt = que.front();
que.pop();
vis[tt] = ;
for(int i=; i<edge1[tt].size(); i++)
{
int mm = edge1[tt][i].v;
if(dist1[mm] > dist1[tt] + edge1[tt][i].cost)
{
dist1[mm] = dist1[tt] + edge1[tt][i].cost;
if(!vis[mm])
{
vis[mm] = ;
que.push(mm);
}
}
}
}
return ;
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("in.txt","r",stdin);
//#endif // ONLINE_JUDGE
scanf("%d %d %d",&n,&m,&p);
int u,v,w;
for(int i=; i<m; i++)
{
scanf("%d %d %d",&u,&v,&w);
addedge(u,v,w);
}
SPFA(p);
int mmax = -INF;
for(int i=; i<=n; i++)
{
if(dist[i] + dist1[i] > mmax && dist[i] != INF && dist1[i]!= INF )
mmax = dist[i] + dist1[i];
}
printf("%d\n",mmax);
return ;
}
最新文章
- 自定义类似MessageBox小窗体操作
- 2016huasacm暑假集训训练五 F - Monkey Banana Problem
- <;转>;iOS性能优化:Instruments使用实战
- 搜索引擎关键词劫持之.net篇
- 以神经网络使用为例的Matlab和Android混合编程
- Varchar2 size how to decide?
- C语言--- 字符串数组 、 预处理器和预处理指令 、 多文件编程 、 结构体
- mybatis15 mapper方式 代码
- 【转载】【挖掘Treap的潜力】
- git仓库迁移和更新远程仓库地址
- Eclipse闪退解决办法
- Dearmweaver CS6 如何添加emmet 插件
- Effective C++_笔记_条款03_尽可能使用const
- [SQL基础教程] 1-5 表的删除和更新
- python——常用模块2
- Android Multimedia框架总结(五)多媒体基础概念
- thinkphp5.0 分页中伪静态的处理
- requestAnimationFrame结束demo
- windows查询占用端口
- 1.Java基础概念.md