hdu--5137--最短路

理解错题意了= =

我看成bfs去做了应该是最短路

一共1-n个点删除 2<=i<=n-1 这些点每次只能删除一个问得到的最短路最大是多少

因为直接放到优先队列不用处理重边的情况

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <utility>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int n;
 9 const int size = 35;
10 bool vis[size];
11 vector< pair<int,int> >ve[size];
12 
13 int dij( int ban )
14 {
15     priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > >q;
16     q.push( make_pair(0,1) );   
17     memset( vis , false , sizeof(vis) );
18     vis[ban] = true;
19     while( !q.empty() )
20     {
21         pair<int,int> now = q.top();
22         q.pop();
23         if( vis[now.second] )
24             continue;
25         vis[now.second] = true;
26         if( now.second==n )
27             return now.first;
28         int veSize = ve[ now.second ].size();
29         for( int i = 0 ; i<veSize ; i++ )
30         {
31             int next = ve[now.second][i].second;
32             int dist = ve[now.second][i].first;
33             if (!vis[next])
34             {
35                 q.push( make_pair( dist+now.first , next) );
36             }
37         }
38     }
39     return -1;
40 }
41 
42 int main()
43 {
44     cin.sync_with_stdio(false);
45     int m , a , b , c , sum , ans;
46     while( cin >> n >> m &&(n||m) )
47     {
48         for( int i = 0 ; i<=n ; i++ )
49             ve[i].clear();
50         for( int i = 0 ; i<m ; i++ )
51         {
52             cin >> a >> b >> c;
53             ve[a].push_back( make_pair(c,b) );
54             ve[b].push_back( make_pair(c,a) );
55         }   
56         ans = -1;
57         for( int i = 2 ; i<=n-1 ; i++ )
58         {
59             sum = dij(i);
60             if( sum==-1 )
61             {
62                 ans = -1;
63                 break;
64             }
65             else
66             {
67                 ans = max( ans , sum );
68             }
69         }
70         if( ans==-1 )
71             cout << "Inf" << endl;
72         else
73             cout << ans << endl;
74     }   
75     return 0;
76 }

View Code