DFS，最优解

解题思路：本题可以用dij算法，但是我感觉dfs更好想，要求最短路径，用递归的话，如果去第2个城市，之前已经去过了，再去一边结果是相同的，所以最优解就是每个城市只去一次，用bool f[N]来判断，然后经行在dfs中加上回溯，即可

注意事项:
设置ans时用0x3f3f3f3f这个最大值容易超时;
参考代码:

#include<bits/stdc++.h>

using namespace std;

#define N  1010

int t[N];//隔离时间;

int w[N][N];

bool f[N];//是否经过;

int n, m;

int ans =10000;//用0x3f3f3f3f容易时间超时;

int nowtime = 0;

void dfs(int step)

{

if (nowtime > ans) return;

if (step == n)

{

ans = min(ans, nowtime);

return;

}

for (int i = 1; i <= n; i++)

{

if (f[i] == false && w[step][i] != 0)

{

nowtime += w[step][i];

f[i] = true;

if (i != n)

{

nowtime += t[i];//加上等待时间;

}

dfs(i);

f[i] = false;

nowtime -= w[step][i];

if (i != n)

{

nowtime -= t[i];

}

}

}

}

int main()

{

cin >> n >> m;

for (int i = 1; i <= n; i++)

{

cin >> t[i];

}

for (int i = 0; i < m; i++)

{

int u, v, time;

cin>>u>>v>>time;

w[u][v] = time;

w[v][u] = time;

}

f[1] = true;

dfs(1);

cout << ans;

}