题意：给定n个点，m条边，求所有顶点中到顶点x的来回最短距离
分析：考虑到数据范围，选用Dijkstra，用Floyd会超时
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int INF=1<<25; 15 const int maxn=1010; 16 struct edge{ 17 int to,cost; 18 }; 19 typedef pair<int,int> P; 20 vector<edge> g[maxn]; 21 int d[maxn]; 22 int dp[maxn][maxn]; 23 int n,m,x; 24 void dijkstra(int s) 25 { 26 priority_queue<P, vector<P>, greater<P> > que; 27 fill(d,d+n+1,INF); 28 d[s]=0; 29 que.push(P(0,s)); 30 while(!que.empty()){ 31 P p=que.top(); que.pop(); 32 int v=p.second; 33 if(d[v]<p.first) continue; 34 for(int i=0;i<g[v].size();i++){ 35 edge e=g[v][i]; 36 if(d[e.to]>d[v]+e.cost){ 37 d[e.to]=d[v]+e.cost; 38 que.push(P(d[e.to],e.to)); 39 } 40 } 41 } 42 } 43 int main() 44 { 45 while(cin>>n>>m>>x) 46 { 47 for(int i=0;i<=n;i++) 48 for(int j=0;j<=n;j++) 49 dp[i][j]=INF; 50 for(int i=0;i<m;i++) 51 { 52 edge e; 53 int a,b,num; 54 scanf("%d%d%d",&a,&b,&num); 55 e.to=b,e.cost=num; 56 g[a].push_back(e); 57 } 58 for(int i=1;i<=n;i++){ 59 dijkstra(i); 60 for(int j=1;j<=n;j++) 61 dp[i][j]=d[j]; 62 } 63 int cnt; 64 int mx=0; 65 for(int i=1;i<=n;i++){ 66 cnt=0; 67 cnt+=dp[i][x]; 68 cnt+=dp[x][i]; 69 mx=max(cnt,mx); 70 } 71 cout<<mx<<endl; 72 } 73 return 0; 74 }