三道编程题

1.骰子展开同一顶点的三个面之和有多少种可能？

枚举即可

2.一台电脑或三台电脑答题计分，最多答多少题？

简单模拟

3.n个点，m条边，k个标记点，s起点，t终点，问从s到t并且经过所有标记点的最短距离？

这个不知道是不是要迪杰斯特拉或者bfs？直接暴力回溯了，但是只过了18%，内存超限制或者是要怎么剪枝呢，我只剪了大于res的情况，路过的AC大佬麻烦评论区说一下呗：）

#include<bits/stdc++.h>
using namespace std;
int res=INT_MAX;
//内存超限制
void dfs(vector<vector<pair<int, int>>>& graph,int path,int kk,int s,int t,vector<int>& mark)
{
    if(kk==0 && s==t)
    {
        res = min(path,res);
        return;
    }
    for(int i=0;i<graph[s].size();++i)
    {
        if(path>res) return;
        auto [r,c] = graph[s][i];
        path += c;
        if(mark[r])
        {
            mark[r]=0;
            dfs(graph,path,kk-1,r,t,mark);
            mark[r]=1;
        }else
        {
            dfs(graph,path,kk,r,t,mark);
        }
        path -= c;
    }
}

int main()
{

    int n,m,k,s,t;
    cin>>n>>m>>k>>s>>t;
    vector<vector<pair<int,int>>> graph(n+1);
    vector<int> mark(n+1,0);
    int kk=k;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
    }
    while(k--)
    {
        int d;
        cin>>d;
        mark[d]=1;
    }
    dfs(graph,0,kk,s,t,mark);
    res = res==INT_MAX?-1:res;
    cout<< res;
}