73. 找最佳通路

★☆   输入文件：city.in   输出文件：city.out   简单对比

时间限制：1 s   内存限制：128 MB

问题描述

有 n 个 城市，它们之间的交通情况已知。现在要求根据一个出发点Cs和一个到达点Cd，请编程序，由计算机找到从城市Cs 到 Cd 的一条路径，要求经过城市最少。

【输入格式】

输入文件： city.in

输入由若干行组成，第一行有四个整数，n（1≤n≤50）、m（1≤m≤n*n）和s（1≤s≤n）、e（1≤e≤n）；n表示城市数，m表示道路数，s和e表示出发点和到达点。

第 2至m+1行是m 条边的 信息，每行两个整数，为边的起点和终点。

【输出格式】

输出文件： city.out

一个整数,经过城市的个数（包括起点和终点）

【输入样例】

输入文件名：city.in

6 6 1 5 

1 3 

2 6 

3 6 

3 2 

6 4 

4 5

输出文件名：city.out

5

 

 

spfa求最短路裸题！

最少经过的城市个数为经过的路的条数-1,。但我们这个地方说的是算上起始结束城市。这样我们得到的经过的城市数为路的条数+1；

我们只需要把边权附成1，然后再跑最短路就好了、

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 1000#define maxn 9999999using namespace std;int n,m,x,y,s,e,tot,ans,dis[N],head[N];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}struct Edge{ int from,to,next,dis;}edge[N];void add(int x,int y,int z){ tot++; edge[tot].to=y; edge[tot].dis=z; edge[tot].next=head[x]; head[x]=tot;}int spfa(int s){ queue
           
            q; bool vis[N]; for(int i=1;i<=n;i++) dis[i]=maxn,vis[i]=false; q.push(s);vis[s]=true;dis[s]=0; while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].next) { int t=edge[i].to; if(dis[x]+edge[i].dis