POJ3268Dijkstra

题意：给定n个点，m条边，求所有顶点中到顶点x的来回最短距离

分析：考虑到数据范围，选用Dijkstra，用Floyd会超时

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <bitset>

 #include <cmath>

 #include <queue>

 #include <stack>

 using namespace std;

 const int INF=<<;

 const int maxn=;

 struct edge{

     int to,cost;

 };

 typedef pair<int,int> P;

 vector<edge> g[maxn];

 int d[maxn];

 int dp[maxn][maxn];

 int n,m,x;

 void dijkstra(int s)

 {

     priority_queue<P, vector<P>, greater<P> > que;

     fill(d,d+n+,INF);

     d[s]=;

     que.push(P(,s));

     while(!que.empty()){

         P p=que.top();  que.pop();

         int v=p.second;

         if(d[v]<p.first)  continue;

         for(int i=;i<g[v].size();i++){

             edge e=g[v][i];

             if(d[e.to]>d[v]+e.cost){

                 d[e.to]=d[v]+e.cost;

                 que.push(P(d[e.to],e.to));

             }

         }

     }

 }

 int main()

 {

     while(cin>>n>>m>>x)

     {

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

                 dp[i][j]=INF;

         for(int i=;i<m;i++)

         {

             edge e;

             int a,b,num;

             scanf("%d%d%d",&a,&b,&num);

             e.to=b,e.cost=num;

             g[a].push_back(e);

         }

         for(int i=;i<=n;i++){

             dijkstra(i);

             for(int j=;j<=n;j++)

                 dp[i][j]=d[j];

         }

         int cnt;

         int mx=;

         for(int i=;i<=n;i++){

             cnt=;

             cnt+=dp[i][x];

             cnt+=dp[x][i];

             mx=max(cnt,mx);

         }

         cout<<mx<<endl;

     }

     return ;

 }