LOJ10075 农场派对

USACO 2007 Feb. Silver

N(1≤N≤1000) 头牛要去参加一场在编号为 x(1≤x≤N) 的牛的农场举行的派对。有 M(1≤M≤100000) 条有向道路，每条路长Ti(1≤Ti≤100)；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这 N 头牛的最短路径（一个来回）中最长的一条的长度。特别提醒：可能有权值不同的重边。

输入格式
第 1 行：3 个空格分开的整数 N,M,X；

第 2…M+1 行：3 个空格分开的整数 Ai,Bi,Ti，表示有一条从Ai 到 Bi 的路，长度为 Ti。

输出格式
一行一个数，表示最长最短路的长度。

样例
样例输入
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
样例输出
10

_______________________________________________________________________________

两次dij，求得起始点到其他点的最短距离。

记得翻边。

_______________________________________________________________________________

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn=1010;

 4 const int maxm=1e5+10;

 5 int n,m,k;

 6 struct edge

 7 {

 8     int u,v,w,nxt;

 9 }e[maxm],ee[maxm];

10 int js,jss,head[maxn],headd[maxn];

11 void addage(int u,int v,int w)

12 {

13     e[++js].u=u;e[js].v=v;e[js].w=w;

14     e[js].nxt=head[u];head[u]=js;

15 }

16 void addagee(int u,int v,int w)

17 {

18     ee[++jss].u=u;ee[jss].v=v;ee[jss].w=w;

19     ee[jss].nxt=headd[u];headd[u]=jss;

20 }

21 int diss[maxn],dis[maxn];

22 bool vis[maxn],viss[maxn];

23 struct node

24 {

25     int dis,p;

26     bool operator < (node b)const

27     {

28         return dis>b.dis;

29     }

30 };

31 void dij(int x)

32 {

33     memset(dis,0x3f,sizeof dis);

34     dis[x]=0;

35     priority_queue< node >q;

36     q.push((node){0,x});

37     while(!q.empty())

38     {

39         node t=q.top();

40         q.pop();

41         int d=t.dis,u=t.p;

42         if(vis[u])continue;

43         vis[u]=1;

44         for(int i=head[u];i;i=e[i].nxt)

45         {

46             int v=e[i].v;

47             if(dis[v]>dis[u]+e[i].w)

48             {

49                 dis[v]=dis[u]+e[i].w;

50                 q.push((node){dis[v],v});

51             }

52         }

53     }

54 }

55 void dijs(int x)

56 {

57     memset(diss,0x3f,sizeof diss);

58     diss[x]=0;

59     priority_queue<node>q;

60     q.push((node){0,x});

61     while(!q.empty())

62     {

63         node t=q.top();

64         q.pop();

65         int d=t.dis,u=t.p;

66         if(viss[u])continue;

67         viss[u]=1;

68         for(int i=headd[u];i;i=ee[i].nxt)

69         {

70             int v=ee[i].v;

71             if(diss[v]>diss[u]+ee[i].w)

72             {

73                 diss[v]=diss[u]+ee[i].w;

74                 q.push((node){diss[v],v});

75             }

76         }

77     }

78 }

79 int main()

80 {

81     scanf("%d%d%d",&n,&m,&k);

82     for(int u,v,w,i=0;i<m;++i)

83     {

84         scanf("%d%d%d",&u,&v,&w);

85         addage(u,v,w);

86         addagee(v,u,w);

87     }

88     dij(k);

89     dijs(k);

90     int ans=0;

91     for(int i=1;i<=n;++i)ans=max(ans,dis[i]+diss[i]);

92     cout<<ans;

93     return 0;

94 }

巴特西

LOJ10075 农场派对

最新文章

热门文章