///其实能还短,然后再改吧
#include <iostream>
#define INF 0x1f1f1f1f
#define N 1005
using namespace std;
int map1[N][N], map2[N][N];//建两个图,一个是另一个的转置
int dis1[N], dis2[N];
bool mark1[N], mark2[N];
int n, m, x;
void init()
{
int i, j;
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
map1[i][j] = INF;
map2[i][j] = INF;
}
map1[i][i] = 0;
map2[i][i] = 0;
}
}
void dijFirst(int start, int n)
{
int i, j, mindis, k;
for(i = 1; i <= n; ++i)
{
dis1[i] = map1[start][i];
mark1[i] = false;
}
dis1[start] = 0;
mark1[start] = true;
while(1)
{
mindis = INF;
for(j = 1; j <= n; ++j)
{
if(!mark1[j] && mindis > dis1[j])
{
mindis = dis1[j];
k = j;
}
}
mark1[k] = true;
if(mindis == INF) break;
for(j = 1; j <= n; ++j)
{
if(!mark1[j] && dis1[j] > dis1[k] + map1[k][j])
dis1[j] = dis1[k] + map1[k][j];
}
}
}
void dijSecond(int start, int n)
{
int i, j, mindis, k;
for(i = 1; i <= n; ++i)
{
dis2[i] = map2[start][i];
mark2[i] = false;
}
dis2[start] = 0;
mark2[start] = true;
while(1)
{
mindis = INF;
for(j = 1; j <= n; ++j)
{
if(!mark2[j] && mindis > dis2[j])
{
mindis = dis2[j];
k = j;
}
}
mark2[k] = true;
if(mindis == INF) break;
for(j = 1; j <= n; ++j)
{
if(!mark2[j] && dis2[j] > dis2[k] + map2[k][j])
dis2[j] = dis2[k] + map2[k][j];
}
}
}
int main()
{
int i, j;
while(cin >> n >> m >> x)
{
init();
for(i = 1; i <= m; ++i)
{
int u, v ,w;
cin >> u >> v >> w;
map2[u][v] = w;
}
int max;
max = 0;
dijSecond(x, n);
///最关键的地方,将矩阵转置以后,从终节点出发到其他节点的距离,就是反向走有向图
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
map1[i][j] = map2[j][i];
}
}
dijFirst(x, n);
for(i = 1; i <= n; ++i)
{
max = (dis1[i] + dis2[i] > max) ? (dis1[i] + dis2[i]) : max;
}
cout << max << endl;
}
//cout << "Hello world!" << endl;
return 0;
}
///一开始只是简单的正搜一次,反搜一次,赵最短路,正搜时用到了循环,dijkstar可是///O(N^2)啊,不超时才怪,之后百度了下,说转置以后的图就是正搜用的图,才吧时间降到115MS,还是水平不够!加油!
///第二次写,memory减少将近一半!!!思想还是一样的,
#include <iostream>
#define INF 0x1f1f1f1f
#define MAX_SIZE 1005
using namespace std;
int map[MAX_SIZE][MAX_SIZE];
int dis[MAX_SIZE];
bool mark[MAX_SIZE];
void init(int n)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
map[i][j] = INF;
map[i][i] = 0;
}
}
void dijkstar(int start, int n)
{
for(int i = 1; i <= n; ++i)
{
dis[i] = map[start][i];
mark[i] = false;
}
dis[start] = 0;
mark[start] = true;
int mindis, tag;
while(1)
{
mindis = INF;
for(int i = 1; i <= n; ++i)
{
if(!mark[i] && mindis > dis[i])
{
mindis = dis[i];
tag = i;
}
}
mark[tag] = true;
if(mindis == INF) break;
for(int i = 1; i <= n; ++i)
{
if(!mark[i] && dis[i] > dis[tag] + map[tag][i])
dis[i] = dis[tag] + map[tag][i];
}
}
}
int main()
{
///需要看看以前的代码,所以还是不够熟,加油!!
int n, m, end;
while(cin >> n >> m >> end)
{
init(n);
int x, y, w;
while(m--)
{
cin >> x >> y >> w;
if(map[x][y] > w)
map[x][y] = w;
}
int sum2[MAX_SIZE];
dijkstar(end, n);
for(int i = 1; i <= n; ++i)
{
sum2[i] = dis[i];
}
int temp;
for(int i = 1; i <= n; ++i)
{
for(int j = i + 1; j <= n; ++j)
{
temp = map[i][j];
map[i][j] = map[j][i];
map[j][i] = temp;
}
}
int sum1[MAX_SIZE];
dijkstar(end, n);
for(int i = 1; i <= n; ++i)
{
sum1[i] = dis[i];
}
int max = -1;
for(int i = 1; i <= n ; ++i)
{
max = (max > sum1[i] + sum2[i]) ? max : sum1[i] + sum2[i];
}
cout << max << endl;
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
Poj中一些题目的源代码,里面共有二十多道题目,OI
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码