题目描述
输入输出格式
输入格式：
文件中第一行有七个数，分别是 S1、 S2 、 …、 S7 ；第二行有两个数，依次分别是起点城市 i 和终点城市 j ；第三行有一个正整数 c ，c<=10000， 表示随后的 c 行中每行存放了一对能直接通达的城市的信息。 能直接通达的城市的信息由三个数组成， 依次分别是两个城市的编号和这两个城市之间的地形。城市的编号都是不超过 100 的正整
数， 但是各个城市的编号未必连续。 文件里同一行中相邻的两个数都是用一个空白字符隔开的。
输出格式：
以一行的形式输出起点城市i 与终点城市 j 之间的最快路线所需要的时间。
输入输出样例
输入样例#1：
0 1 0 0 0 0 0
1 4
4
1 2 1
1 3 1
2 4 2
3 4 3
输出样例#1：
5
思路：spfa搞一下就可以了。
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 10010
using namespace std;
queue<int>que;
int S[];
int s,t,m,tot;
int dis[MAXN],vis[MAXN];
int num[]={,,,,,,,};
int to[MAXN*],cap[MAXN*],net[MAXN*],head[MAXN];
void add(int u,int v,int w){
to[++tot]=v;net[tot]=head[u];cap[tot]=w;head[u]=tot;
to[++tot]=u;net[tot]=head[v];cap[tot]=w;head[v]=tot;
}
void spfa(int s){
memset(vis,,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
que.push(s);
vis[s]=;dis[s]=;
while(!que.empty()){
int now=que.front();
que.pop();
vis[now]=;
for(int i=head[now];i;i=net[i])
if(dis[to[i]]>dis[now]+cap[i]){
dis[to[i]]=dis[now]+cap[i];
if(!vis[to[i]]){
vis[to[i]]=;
que.push(to[i]);
}
}
}
}
int main(){
for(int i=;i<=;i++) scanf("%d",&S[i]);
scanf("%d%d",&s,&t);
scanf("%d",&m);
for(int i=;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(S[z]==) add(x,y,num[z]/);
else add(x,y,num[z]);
}
spfa(s);
cout<<dis[t];
}