[PAT Advanced Level]1003. Emergency (25) - c++编程基础

利用深度优先搜索获得最短路径以及最多的支援。

看到有人是先用Dijstra算法获得最短路径，再用DFS求得最短路径的条数，这个以后再实现。

#include   
#include   
#include   
using namespace std;  
  
int city, pathNum, start, dis;  
int *teams;  
int path[501][501] = {0};  
bool isVisited[501] = {false};  
  
int mini = 999999999;  
int current = 0;  
int miniNum = 0;  
int currentTeam = 0;  
int totalTeam = 0;  
vector v;  
  
void DFS(int begin);  
  
int main()  
{  
    //fstream cin("a.txt");  
  
    cin>>city>>pathNum>>start>>dis;  
    teams = new int[city];  
    for(int i = 0; i < city; i++)  
        cin>>teams[i];  
    for(int i = 0; i < pathNum; i++)  
    {  
        int a,b,c;  
        cin>>a>>b>>c;  
        path[a][b] = c;  
        path[b][a] = c;  
    }  
    v.push_back(start);  
    isVisited[start] = true;  
    DFS(start);  
    isVisited[start] = false;  
    v.pop_back();  
  
    cout<




currentTeam   totalTeam = totalTeam : totalTeam = currentTeam;  
        }  
        currentTeam = current = 0;  
    }  
    else  
    {  
        for(int i = 0; i < 501; i++)  
        {  
            if(!isVisited[i] && path[begin][i] != 0)  
            {  
                isVisited[i] = true;  
                v.push_back(i);  
                DFS(i);  
                v.pop_back();  
                isVisited[i] = false;  
            }  
        }  
    }  
}