1.学习迪杰斯特拉算法 2.听学长讲课 3.完成两道题
（1）.[USACO08OPEN]Clear And Present Danger S - 洛谷
FLOYD算法模板题。
#include#includeusing namespace std;int dis[1000][1000],order[1000100];int main(){ int n,m,i,j,k,sum=0; cin>>n>>m; for(i=1;i<=m;i++) cin>>order[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> dis[i][j]; for(k = 1; k <= n; k++) for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); sum = dis[1][order[1]]; for(i = 2; i <= m; i++) sum += dis[order[i - 1]][order[i]]; sum += dis[order[m]][n]; cout << sum<
题目要求行经路径中包含指定路径，那么在使用floyd算法更新完所有最短路径后，再用循环加上“走过指定路径”的危险度，就可以得到答案了。
（2）.炸铁路 - 洛谷
这题似乎与我们现在学的知识点没什么太大的关系，不用最短路的算法。我用的并查集算法。
由于题目说最终的输出答案须要按照a的大小顺序输出，如果a相同就按b的大小顺序，而且如果a>b就要交换顺序。
所以我们在输入时先保证左边的值一定小于右边的值，输入完后再重新排序一遍。
而后就是逐个遍历，去掉某条路线时再将其它路线利用并查集链接，检查是否会出现“无法到达某个城市”的情况，如果出现那么就说明这条路线符合题目要求
#includeusing namespace std;int n,m,fla,parent[10001],flag;struct abc{int a,b;}ans[20000];bool cmp(abc a,abc b){ if(a.a>ans[i].a>>ans[i].b; if(ans[i].a>ans[i].b)swap(ans[i].a,ans[i].b); } sort(ans+1,ans+m+1,cmp); for(int i=1;i<=m;i++) { flag=0; for(int j=1;j<=n;j++)parent[j]=j; for(int j=1;j<=m;j++) if(i != j) unionn(ans[j].a,ans[j].b); if(flag != n-1)printf("%d %dn",ans[i].a,ans[i].b); } return 0;}