题目链接
第一次敲的时候我用的是vector，看题的时候心里还在想着要判重边，把代码都敲完后发现了问题，用vector没办法判断重边啊~又把数据结构赶紧改成了邻接矩阵，同时也发现了自己容易犯的错误！学了新东西就只用新的，不善于思考两者的优劣势，（工欲善其事必先利其器）这句话自己没做到！！真是大忌啊！！！
还有一点就是今天学会了怎么去计算是否超内存了！这一点对于我做题时候选择数据结构时非常有用
#include<stdio.h> #include<string.h> #include<queue> using namespace std; #define inf 0x3f3f3f #define min(a,b) a<b?a:b int map[1005][1005]; int dis[1005]; int vis[1005]; int spfa(int s,int q,int n) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); int v,i,w,u; queue<int>Q; Q.push(s); vis[s]=1; dis[s]=0; while(!Q.empty()) { u=Q.front(); Q.pop(); for(v=1;v<=n;v++) { if(map[u][v]<inf) { if(dis[v] > dis[u]+map[u][v]) { dis[v]=dis[u]+map[u][v]; if(!vis[v]) { vis[v]=1; Q.push(v); } } } } } return dis[q]; } int main() { int T; scanf("%d",&T); while(T--) { int n,m,p,q,i; int army[105]; memset(army,0,sizeof(army)); memset(map,0x3f,sizeof(map)); scanf("%d%d%d%d",&n,&m,&p,&q); for(i=1;i<=m;i++) map[i][i]=0; for(i=1;i<=n;i++) { scanf("%d",&army[i]); } for(i=0;i<p;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w);//需要判重边 map[u][v]=map[v][u]=min(map[u][v],w); } int min=1<<28; for(i=1;i<=n;i++) { int res=spfa(army[i],q,m); if(min>res) { min=res; } } printf("%d\n",min); } return 0; }