題目大意：給出一個單向帶權圖和一個點s，求點u，u到s的最短路徑和s到u的最短路徑之和最大。
對於s到任意點的最短路，直接dijkstra可以求出。
對於任意點到s的最短路，如果將所有邊反向然後求一次最短路，容易證明，求出的s到任意點v的最短路s-->v就是原來沒有反向的圖的v-->s的最短路。
所以先求一次dijkstra，保存此次的結果，然後把所有的邊反向，權值不變，再求一次dijkstra，將兩次結果加起來，計算它們之中的最大值。
#include
#include
#include
#include
using namespace std;
const int maxn=1010;
const int INF=(1<<29);
struct edge
{
int to;
int dis;
};
struct edge2
{
int from;
int to;
int dis;
};
struct heapnode
{
int di;
int num;
bool operator< (const heapnode j) const
{
return di>j.di;
}
};
edge2 e[100010];
int d[maxn];
int sum[maxn];
int use[maxn];
int n;
vector G[maxn];
void dijkstra(int s);
int main(void)
{
int i,u,v,p,q,m,ans;
edge ed;
while(scanf("%d%d%d",&n,&m,&q)==3)
{
for(i=1;i<=n;i++)
{
G[i].clear();
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&p);
ed.to=v;
ed.dis=p;
G[u].push_back(ed);
e[i].from=u;
e[i].to=v;
e[i].dis=p;
}
dijkstra(q);
for(i=1;i<=n;i++)
{
sum[i]=d[i];
G[i].clear();
}
for(i=1;i<=m;i++)
{
ed.to=e[i].from;
ed.dis=e[i].dis;
G[e[i].to].push_back(ed);
}
dijkstra(q);
ans=0;
for(i=1;i<=n;i++)
{
ans=d[i]+sum[i]>ans?d[i]+sum[i]:ans;
}
printf("%d\n",ans);
}
return 0;
}
void dijkstra(int s)
{
int i,u,p;
heapnode h;
priority_queue heap;
for(i=1;i<=n;i++)
{
d[i]=INF;
use[i]=0;
}
h.di=0;
h.num=s;
d[s]=0;
heap.push(h);
while(heap.empty()==false)
{
h=heap.top();
heap.pop();
u=h.num;
if(use[u]==0)
{
use[u]=1;
p=G[u].size();
for(i=0;i
