最短路最基础的题啦，刚学会拿来练习~~~

用的Dijkstra算法【目前就会这一个Orz

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAX = 105;const int INF = 0x7ffffff;int mp[MAX][MAX];int vis[MAX];int dis[MAX];int dij(int n){    int m, k;    memset(vis, 0, sizeof(vis));    for (int i = 0; i < n; i++)    {        dis[i] = mp[0][i];    }    vis[0] = 1;    for (int i = 1; i < n; i++)    {        m = INF;        k = 1;        for (int j = 0; j < n; j++)        {            if (!vis[j] && m > dis[j])            {                m = dis[j];                k = j;            }        }        vis[k] = 1;        if (k == n - 1)            return m;        for (int j = 0; j < n; j++)        {            if (!vis[j] && dis[j] > dis[k] + mp[k][j])            {                dis[j] = dis[k] + mp[k][j];            }        }    }    return dis[n - 1];}int main(){    int m, n;    int a, b, c;    while (scanf("%d%d", &n, &m) == 2 && (m || n))    {        for (int i = 0; i < n; i++)        {            for (int j = 0; j < n; j++)            {                if (i == j)                    mp[i][j] = 0;                else                    mp[i][j] = INF;            }        }        for (int i = 0; i < m; i++)        {            scanf("%d%d%d", &a, &b, &c);            if (mp[a - 1][b - 1] > c)                mp[a - 1][b - 1] = mp[b - 1][a - 1] = c;        }        int ans = dij(n);        printf("%d\n", ans);    }    return 0;}
       
      
     

我目前理解的Dijkstra算法就是用一个数组（dis[]）来存各点到起点的距离，然后找一个离起点最近的点，标记访问，（vis[]）用这个点来刷新其他点到起点的距离，然后继续找一个离起点，循环，直到终点被访问~

有一点不明白，0x7fffffff不是int的最大值么，为什么我const int INF = 0x7fffffff;就WAconst int INF = 0x7ffffff;就AC了……记得问问学长……

——————更新分割线————-

用0x7f7777777会WA的原因是因为已经是int的最大值，再加一个数就溢出了。

for (int j = 0; j < n; j++){    if (!vis[j] && dis[j] > dis[k] + mp[k][j])    {
             dis[j] = dis[k] + mp[k][j];    }}

就是这里。

要保证不溢出就要比int小路径最长值，此题的话，每条路径长度范围C（1<=C<=1000），路口数N（N<=100），所以INF最大也只能是int最大值减C*N，即

const int INF = 0x7fffffff - 1000 * 100;

^ ^~欢迎批评指正~~