通过引入奖励机制和非完全贪心策略，改进Dijkstra算法并写出它的算法代码

改进Dijkstra算法需要引入奖励机制和非完全贪心策略，具体步骤如下：

1. 初始化距离数组dist[]和标记数组visited[]，将起点s的dist[s]设为0，visited[s]设为true，其余点的dist[]初始值为无穷大，visited[]初始值为false。

2. 设置奖励系数reward，用于在选择路径时考虑一些非最短路径，避免陷入局部最优解。

3. 进行n-1次松弛操作，每次找到当前未标记的距离最小的点u，将其标记为visited[u] = true，并更新其邻接点v的距离dist[v] = min(dist[v], dist[u] + w(u,v)*reward)，其中w(u,v)表示u到v的边权重。

4. 返回起点s到各个点的最短路径dist[]。

下面是改进后的Dijkstra算法的代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

vector<pair<int, int>> adj[1001];
int dist[1001];
bool visited[1001];

void dijkstra(int s, int n, int reward) {
    memset(dist, INF, sizeof(dist));
    memset(visited, false, sizeof(visited));
    dist[s] = 0;
    visited[s] = true;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto v : adj[u]) {
            if (!visited[v.first] && dist[u] + v.second*reward < dist[v.first]) {
                dist[v.first] = dist[u] + v.second*reward;
                pq.push(make_pair(dist[v.first], v.first));
            }
        }
        visited[u] = true;
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
    }
    dijkstra(s, n, 2); // 奖励系数为2
    for (int i = 1; i <= n; i++) {
        if (dist[i] < INF) cout << dist[i] << endl;
        else cout << "INF" << endl;
    }
    return 0;
}