题目链接：

　　

题目描述：

　　有n个交叉口，m条路，每条路有三个属性：起点，终点，最大载重。假设从a到b的最大载重是从a—>b所能承载的最大重量，问从1—>n的最大载重是多少？

解题思路：

　　利用dijkstra的变形，dist数组里存的不再是最短路径了，而是最大载重，也许描述的不是很清楚，但是代码很清楚。

ps：类似的题目在今年省赛时候见过，当时刚接触图，所以就想用排序+并查集做，这道题目的做法很多，不止这两种。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 #define maxn 1010 8  9 int n, m;10 int map[maxn][maxn], vis[maxn], dist[maxn];11 void dijkstra ();12 13 int main ()14 {15     int i, j, l = 0, a, b, s, ncase;16     scanf ("%d", &ncase);17 18     while (ncase --)19     {20         scanf ("%d %d", &n, &m);21         memset (map, 0, sizeof(map));//注意数组的初始化22 23         for (i=0; i
          
            dist[j])//若能扩大j的最大载重值，则扩大63 dist[j] = temp;64 }65 }66 }67 }