PTA上一个最短路问题调了半天还差一个测试点，实在是服气了，思路很简单没问题，算法也没问题，不断被卡测试点将近怀疑人生，最后开大数组通过，猛然醒悟，然后觉得自己太菜了。

最短路这方面的题我之前做了不过6道，没在这上面下功夫，这次不断卡测试点确实是活该。

用的链式前向星存图，但我没用vector，存边开的结构数组，最多500个点，无向图，又犯了高中的老毛病：读题不仔细，题里说点的数量小于等于500（2≤N≤500），这次想当然看成了(2≤N,M≤500)，M是边的数量，结构数组只开了2010，实际上跑一个循环就能知道500个点最多能有多少条不重复的边。

题目实际没说最多有多少边的时候实际上也是可以求出来的，用邻接矩阵或者用vector实现链式前向星就不用考虑这个问题。

1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;
int main(){
    int res=0;
    for(int i=1;i<=499;i++) res+=i;
    cout<<res<<endl;
    return 0;
}
//输出124750

最短路问题做题过少，就6道题基本就相当于没有，还处于理论阶段，没有落实，接下来得专门练习练习这方面。